title: Kolakoski Reduction

text:
# Question
Title: Kolakoski Reduction
# Overview

Some of you might be aware of the Kolakoski Sequence (A000002), a well know self-referential sequence that has the following property:

It is a sequence containing only 1's and 2's, and for each group of 1's and twos, if you add up the length of runs, it equals itself, only half the length. In other words, the Kolakoski sequence describes the length of runs in the sequence itself. It is the only sequence that does this except for the same sequence with the initial 1 deleted. (This is only true if you limit yourself to sequences made up of 1s and 2s - Martin Ender)

---

# The Challenge

The challenge is, given a list of integers:

* Output `-1` if the list is NOT a working prefix of the Kolakoski sequence.
* Output the number of iterations before the sequence becomes `[2]`.

---

# The Worked Out Example

Using the provided image as an example:

```
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1] # Iteration 0 (the input).
[1,2,2,1,1,2,1,2,2,1,2]             # Iteration 1.
[1,2,2,1,1,2,1,1]                   # Iteration 2.
[1,2,2,1,2]                         # Iteration 3.
[1,2,1,1]                           # Iteration 4.
[1,1,2]                             # Iteration 5.
[2,1]                               # Iteration 6.
[1,1]                               # Iteration 7.
[2]                                 # Iteration 8.

```

Therefore, the resultant number is `8` for an input of `[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]`.

`9` is also fine if you are 1-indexing.

---

# The Test Suite (You can test with sub-iterations too)

```
------------------------------------------+---------
Truthy Scenarios                          | Output
------------------------------------------+---------
[1,1]                                     | 1 or 2
[1,2,2,1,1,2,1,2,2,1]                     | 6 or 7
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]       | 8 or 9
[1,2]                                     | 2 or 3
------------------------------------------+---------
Falsy Scenarios                           | Output
------------------------------------------+---------
[4,2,-2,1,0,3928,102904]                  | -1 or a unique falsy output.
[1,1,1]                                   | -1
[2,2,1,1,2,1,2] (Results in [2,3] @ i3)   | -1 (Trickiest example)
[]                                        | -1
[1]                                       | -1

```

If you're confused:

**Truthy:** It will eventually reach two without any intermediate step having any elements other than `1` and `2`. – `Einkorn Enchanter 20 hours ago`

**Falsy:** Ending value is not `[2]`. Intermediate terms contain something other than something of the set `[1,2]`. A couple other things, see examples.

---

This is , lowest byte-count will be the victor.

# Answer
# Haskell, ~~126~~ ~~87~~ ~~79~~ ~~76~~ 75 bytes

*39 bytes saved thanks to Ørjan Johansen*

```
import Data.List
f[2]=0
f y@(_:_:_)|all(`elem`[1,2])y=1+f(length<$>group y)

```

Try it online!

This errors on bad input.
> 8 votes

# Answer
# 05AB1E, 22 bytes

```
[Dg2‹#γ€gM2›iX]2QJiNë®

```

Try it online!

**Explanation**

```
[                        # start a loop
 D                       # duplicate current list
  g2‹#                   # break if the length is less than 2
      γ                  # group into runs of consecutive equal elements
       €g                # get length of each run
         M2›iX           # if the maximum run-length is greater than 2, push 1
              ]          # end loop
               2QJi      # if the result is a list containing only 2
                   N     # push the iteration counter from the loop
                    ë®   # else, push -1
                         # implicitly output top of stack

```
> 7 votes

# Answer
# Jelly, 17 bytes

```
ŒgL€$ÐĿµẎḟ1,2ȯL_2

```

Try it online!
> 4 votes

# Answer
# SCALA, 290(282?) chars, 290(282?) bytes

It took me sooo loong ... But I'm finally done!

with this code :

```
var u=t
var v=Array[Int]()
var c= -1
var b=1
if(!u.isEmpty){while(u.forall(x=>x==1|x==2)){c+=1
if(u.size>1){var p=u.size-1
for(i<-0 to p){if(b==1){var k=u(i)
v:+=(if(i==p)1 else if(u(i+1)==k){b=0
if(p-i>1&&u(i+2)==k)return-1
2}else 1)} else b=1}
u=v
v=v.take(0)}else if(u(0)==2)return c}}
c

```

I don't know if I should count the `var u=t` into the bytes, considering I do not use `t` during the algorithm (the copy is just to get a modifyable `var` instead of the parameter `t` considered as `val` \- thanks *ScaLa*). Please tell me if I should count it.

Hard enough. Try it online!

PS : I was thinking of doing it recursively, but I'll have to pass a counter as a parameter of the true recursive "subfunction" ; this fact makes me declare two functions, and these chars/bytes are nothing but lost.

EDIT : I had to change (?) because we're not sure we should take in count `[1]` case. So here is the modified code :

```
var u=t
var v=Array[Int]()
var c= -1
var b=1
if(!u.isEmpty){try{t(1)}catch{case _=>return if(t(0)==2)0 else -1}
while(u.forall(x=>x==1|x==2)){c+=1
if(u.size>1){var p=u.size-1
for(i<-0 to p){if(b==1){var k=u(i)
v:+=(if(i==p)1 else if(u(i+1)==k){b=0
if(p-i>1&&u(i+2)==k)return-1
2}else 1)} else b=1}
u=v
v=v.take(0)}else if(u(0)==2)return c}}
c

```

It's not optimized (I have a duplicate "out" for the same conditions : when I get to `[2]` and when param is `[2]` is treated separatedly).

NEW COST = 342 (I didn't modify the title on purpose)
> 3 votes

# Answer
# Jelly, ~~26~~ ~~25~~ ~~22~~ ~~21~~ 20 bytes

```
FQœ-2R¤
ŒgL€µÐĿṖ-LÇ?

```

Try it online!

This code actually wasn't working correctly until 20 bytes and I didn't even notice; it was failing on the `[2,2]` test case. Should work perfectly now.
> 3 votes

# Answer
# Jelly, 12 bytes

```
ŒɠƬµ2Wea’ỊȦƊ

```

Try it online!

## How it works

```
ŒɠƬµ2Wea’ỊȦƊ - Main link. Takes a list L on the left
  Ƭ          - Until reaching a fixed point, keeping each step:
Œɠ           -   Get the lengths of consectuively equal groups of elements
   µ         - Call this list S and use it as the argument
    2W       - Yield [2]
      e      - Is [2] in S?
           Ɗ - Last 3 links as a monad f(S):
        ’    -   Decrement every integer in S
         Ị   -   Insignificant? Replace 0 and 1 with 1, everything else 0
          Ȧ  -   Any and all? S is non-empty and has no zeros
       a     - Both are true?

```
> 3 votes

# Answer
# **JavaScript, ~~146~~ 142 bytes**

First try in code golfing, it seems that the "return" in the larger function is quite tedious...

Also, the checking of b=1 and b=2 takes up some bytes...

Here's the code:

```
f=y=>{i=t=!y[0];while(y[1]){r=[];c=j=0;y.map(b=>{t|=b-1&&b-2;if(b-c){if(j>0)r.push(j);c=b;j=0}j++});(y=r).push(j);i++}return t||y[0]-2?-1:0^i}

```

Explanation

```
f=y=>{/*1*/}                                        //function definition

//Inside /*1*/:
  i=t=!y[0];                                        //initialization
                                                    //if the first one is 0 or undefined,
                                                    //set t=1 so that it will return -1
                                                    //eventually, otherwise i=0
  while(y[1]){/*2*/}                                //if there are 2+ items, start the loop

  //Inside /*2*/:
    r=[];c=j=0;                                     //initialization
    y.map(b=>{/*3*/});                              //another function definition

    //Inside /*3*/:
      t|=b-1&&b-2;                                  //if b==1 or b==2, set t=1 so that the
                                                    //entire function returns -1
      if(b-c){if(j>0)r.push(j);c=b;j=0}             //if b!=c, and j!=0, then push the
                                                    //count to the array and reset counter
      j++                                           //counting duplicate numbers

    (y=r).push(j);i++                               //push the remaining count to the array
                                                    //and proceed to another stage

  return t||y[0]-2?-1:0^i                           //if the remaining element is not 2, or
                                                    //t==1 (means falsy), return -1,
                                                    //otherwise return the counter i

```

Test data (using the given test data)

```
l=[[1,1],[1,2,2,1,1,2,1,2,2,1],[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1],[1,2],[4,2,-2,1,0,3928,102904],[1,1,1],[2,2,1,1,2,1,2],[]];
console.log(l.map(f));
//Output: (8) [1, 6, 8, 2, -1, -1, -1, -1]

```

Edit 1: 146 -\> 142: Revoking my edit on reducing bytes, because this affects the output; and some edit on the last statement
> 2 votes

# Answer
## JavaScript (ES6), ~~127~~ ~~126~~ ~~95~~ 80 bytes

```
g=(a,i,p,b=[])=>a.map(x=>3>x&0<x?(x==p?b[0]++:b=[1,...b],p=x):H)==2?i:g(b,~~i+1)

```

0-indexed. Throws `"ReferenceError: X is not defined"` and `"InternalError: too much recursion"` on bad input.

### Test cases

```
g=(a,i,p,b=[])=>a.map(x=>3>x&0<x?(x==p?b[0]++:b=[1,...b],p=x):H)==2?i:g(b,~~i+1)

function wrapper(testcase) {
  try {console.log(g(testcase))} catch(e) {
    console.log("Error")
  }
}

wrapper([1,1])
wrapper([1,2,2,1,1,2,1,2,2,1])
wrapper([1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1])
wrapper([1,2])
wrapper([4,2,-2,1,0,3928,102904])
wrapper([1,1,1])
wrapper([2,2,1,1,2,1,2])
wrapper([])
wrapper([1])
```
> 2 votes

# Answer
# Scala 3 (compile-time), 460 bytes

This may be the longest answer here, but it's also the fastest one here...because it works at compile time.

```
import compiletime.ops.int._
type r[T,P]=T match{case h*:t=>r[t,h*:P]case E=>P}
type E=EmptyTuple
type F[K,R,L,S,P,I]=K match{case E=>L-S match{case 0=>R match{case E=>0 case _=>F[r[R,E],E,0,0,0,I+1]}case _=>0}case P*:_=>0
case 1*:1*:t=>F[t,2*:R,L+2,S+2,1,I]case 1*:t=>(t,R)match{case(E,E)=>0 case _=>F[t,1*:R,L+1,S+1,1,I]}case 2*:2*:t=>F[t,2*:R,L+2,S+2,2,I]case 2*:t=>(t,R)match{case(E,E)=>I+1 case _=>F[t,1*:R,L+1,S+1,2,I]}case _=>0}
type G[K]=F[K,E,0,0,0,0]

```

Try it in online!

You can invoke it as `G[1 *: 2 *: EmptyTuple]` (actually, just `G[(1, 2)]` *should* also work, but for whatever reason, it's not working right now. I'll fix it later, though). It's 1-indexed, and it returns 0 for falsy inputs.
> 2 votes

# Answer
# Python 2, ~~184 163~~ 156 bytes

* @Felipe Nardi Batista saved 21 bytes!!!! thanks a lot!!!!
* **Halvard Hummel saved 7 bytes!! thanks**

# Python 2, 156 bytes

```
a,c=input(),0
t=a==[]
while 1<len(a)and~-t:
 r,i=[],0
 while i<len(a):
	j=i
	while[a[j]]==a[i:i+1]:i+=1
	r+=[i-j]
 a=r;c+=1;t=any(x>2for x in a)
print~c*t+c

```

Try it online!

Explanation:

```
a,c=input(),0                             #input and initialize main-counter

t=a==[]                                   #set t to 1 if list's empty.

while len(a)>1:                           #loop until list's length is 1.

 r,i=[],0                                 #Initialize temp. list and
                                          #list-element-pointer

 while i<len(a):                          #loop for the element in list

  j=0                                     #set consecutive-item-counter to 0

  while(i+j)<len(a)and a[i]==a[i+j]:j+=1  #increase the consec.-counter

  r+=[j];i+=j                             #add the value to a list, move the
                                          #list-element-pointer

 a=r;c+=1;t=any(x>2for x in a)            #update the main list, increase t
                                          #the counter, check if any number
 if t:break;                              #exceeds 2 (if yes, exit the loop)

print[c,-1][t]                            #print -1 if t or else the
                                          #counter's
                                          #value

```
> 1 votes

# Answer
## Clojure, 110 bytes

```
#(if-not(#{[][1]}%)(loop[c % i 0](if(every? #{1 2}c)(if(=[2]c)i(recur(map count(partition-by + c))(inc i))))))

```

A basic `loop` with a pre-check on edge cases. Returns `nil` for invalid inputs. I did not know `(= [2] '(2))` is `true` :o
> 1 votes

# Answer
# Python 2, 146 bytes (function only)

```
f=lambda l,i=0:i if l==[1]else 0if max(l)>2or min(l)<1else f([len(x)+1for x in"".join(`v!=l[i+1]`[0]for i,v in enumerate(l[:-1])).split("T")],i+1)

```

Returns 0 on falsy input (ok since it's 1-indexed). Simply use it like this:

```
print(f([1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]))

```
> 1 votes

# Answer
## Mathematica, 82 bytes

```
FixedPointList[#/.{{2}->T,{(1|2)..}:>Length/@Split@#,_->0}&,#]~FirstPosition~T-1&

```

`Function` which repeatedly replaces `{2}` with the undefined symbol `T`, a list of (one or more) `1`s and `2`s with the next iteration, and anything else with `0` until a fixed point is reached, then returns the `FirstPosition` of the symbol `T` in the resulting `FixedPointList` minus `1`. Output is `{n}` where `n` is the (`1`-indexed) number of iterations needed to reach `{2}` for the truthy case and `-1+Missing["NotFound"]` for the falsy case.

If the output must be `n` rather than `{n}`, it costs three more bytes:

```
Position[FixedPointList[#/.{{2}->T,{(1|2)..}:>Length/@Split@#,_->0}&,#],T][[1,1]]-1&

```
> 1 votes

# Answer
# R, 122 bytes

```
a=scan()
i=0
f=function(x)if(!all(x%in%c(1,2)))stop()
while(length(a)>1){f(a)
a=rle(a)$l
f(a)
i=i+1}
if(a==2)i else stop()

```

Passes all test cases. Throws one or more errors otherwise. I hate validity checks; this code could have been so golfed if the inputs were nice; it would be shorter even in case the input were a sequence of 1’s and 2’s, not necessarily a prefix of the Kolakoski sequence. Here, we have to check both the initial vector (otherwise the test case `[-2,1]`) would have passed) and the resulting vector (otherwise `[1,1,1]` would have passed).
> 1 votes

# Answer
# Python 2, 122 bytes

```
def f(s,c=2,j=0):
 w=[1]
 for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
 return(w==[2])*c-({1,2}!=set(s))or f(w,c+1)

```

Try it online!

# Python 3, 120 bytes

```
def f(s,c=2,j=0):
 w=[1]
 for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
 return(w==[2])*c-({1,2}!={*s})or f(w,c+1)

```

Try it online!

# Explanation

A new sequence (w) is initialized to store the next iteration of the reduction. A counter (c) is initalized to keep track of the number of iterations.

Every item in the original sequence (s) is compared to the previous value. If they are the same, the value of the last item of (w) is increased with 1. If they are different, the sequence (w) is extended with \[1\].

If w==\[2\], the counter (c) is returned. Else, if the original sequence (s) contains other items than 1 and 2, a value -1 is returned. If neither is the case, the function is called recursively with the new sequence (w) as (s) and the counter (c) increased by 1.
> 1 votes

# Answer
# Stax, 26 bytes

```
äE⌐+É7∩ΦΓyr╔ßΣ·φƒÇe►ef%I»

```

Run and debug it

Tried with a generator, but it seems like a while loop is shorter.
> 1 votes

# Answer
# , ~~93~~ 92 bytes

*Edit: -1 byte thanks to Giuseppe*

```
f=function(x)`if`(sum(x|1)<2,(-1)^(sum(x)!=2),`if`(!all(x%in%1:2),-1,(y=f(rle(x)$l))+(y>0)))

```

Try it online!

Returns 1-based number of iterations for truthy input, and `-1` for all falsy inputs. This needed quite careful input testing, especially for the last two test cases...

**Commented:**

```
f=function(x)           # recursive function with argument x
`if`(sum(x|1)<2,        # if there's one (or less) element left
  (-1)^(sum(x)!=2),     # return 1 if it's equal to 2, -1 otherwise
  `if`(!all(x%in%1:2),  # if any element isn't 1 or 2
    -1,                 # return -1
    (y=f(               # otherwise recursively call self with
      rle(x)$l))        # lengths of groups of digits in x
      +(y>0)))          # if result is positive, return result +1
                        # otherwise return result (which must be -1)

```

---

# , ~~74~~ 66 bytes

```
f=function(x)`if`(sum(x)==2&x==2,1,if(all(x%in%1:2))f(rle(x)$l)+1)

```

Try it online!

...but then I read the comments more carefully and realised that it's Ok to output nothing, or rubbish, or to error for falsy inputs. That makes it much easier!
> 1 votes

# Answer
# Vyxal, 30 bytes

```
λĠvL&›Dƛ2>;A$Ḣ∧[x|u£];†h2=[¥|u

```

Try it Online!

A big mess.
> 1 votes

# Answer
# Ruby, ~~81~~ 77 bytes

```
f=->a,i=1{a[1]&&a-[1,2]==[]?f[a.chunk{|x|x}.map{|x,y|y.size},i+1]:a==[2]?i:0}

```

Try it online!

**Edit:** Saved 4 bytes by converting to recursive lambda.

Returns 1-indexed number of iterations or 0 as falsey.

Makes use of Ruby enumerable's chunk method, which does exactly what we need - grouping together consecutive runs of identical numbers. The lengths of the runs constitute the array for the next iteration. Keeps iterating while the array is longer than 1 element and no numbers other than 1 and 2 have been encountered.
> 0 votes

# Answer
# Pyth, 45 bytes

```
L?||qb]1!lb-{b,1 2_1?q]2b1Z.V0IKy~QhMrQ8*KhbB

```

Try it online!

This is probably still golfable. It's definitely golfable if `.?` worked the way I hoped it would (being an `else` for the innermost structure instead of the outermost)

```
L?||qb]1!lb-{b,1 2_1?q]2b1Z # A lambda function for testing an iteration of the shortening
L                           # y=lambda b:
 ?                          # if
    qb]1                    #    b == [1]
   |    !lb                 #      or !len(b)
  |         {b              #        or b.deduplicate()
           -  ,1 2          #             .difference([1,2]):
                  _1        #               return -1
                    ?q]2b1Z # else: return 1 if [2] == b else Z (=0)

.V0                         # for b in range(0,infinity):
   IKy~Q                    # if K:=y(Q :=        (applies y to old value of Q)
        hM                  #    map(_[0],
          rQ8               #               run_length_encode(Q)):
             *Khb           #    print(K*(b+1))
                 B          #    break

```
> 0 votes

# Answer
# Perl 5 `-p`, 71 bytes

```
$_.=$";s/(. )\1*/$&=~y|12||.$"/ge&$.++while/^([12] ){2,}$/;$_=/^2 $/*$.

```

Try it online!

`1`-indexed. Outputs `0` for falsy.
> 0 votes

---
Tags: code-golf, sequence
---


title: Print a Negative of your Code

text:
# Question
Title: Print a Negative of your Code
Consider a square of printable ASCII characters (code points 0x20 to 0x7E) for side length **N**, like the following (here, **N = 6**):

```
=\
 g \
7
m+y "g
  L ~
e> PHq

```

We also require **each row** and **each column** to contain at least **1 space** and **1 non-space** character. (The above example satisfies this.)

We define the **negative** of such a square, to be a square of the same size, where each space is replaced with a non-space and vice versa. E.g., the following would be a valid negative of the above example:

```
  1234
a b cd
 ZYXWV
   !
{} [ ]
  ?

```

The choice of non-space characters is irrelevant (as long as they are from the printable ASCII range).

## The Challenge

You're to write a program, with square source code with side length **N \> 1**, which prints a negative of itself to STDOUT. Trailing spaces *have* to be printed. You may or may not print a single trailing newline.

The usual quine rules also apply, so you must not read your own source code, directly or indirectly. Likewise, you must not assume a REPL environment, which automatically prints the value of each entered expression.

The winner is the program with the lowest side length **N**. In the event of a tie, the submission with the fewest non-space characters in the source code wins. If there's still a tie, the earliest answer wins.

# Answer
> 19 votes
# CJam, 4 x 4 (8 non-spaces)

```
 L _
{ _
 _ }
_ p

```

Try it online in the CJam interpreter.

### Output

```
{ _
 _ }
{ _
 _ }

```

### How it works

* `L` pushes an empty array and `_` pushes a copy of it.
* The block

```
{ _
 _ }

```

pushes that block on the stack.
* `_` pushes a copy of the code block and `p` prints it, followed by a linefeed.
* Finally, the interpreter prints all remaining items on the stack: two empty arrays that do not affect the output, and the original code block.

## Alternate version

```
 L ~
{ _
 p }
_ ~

```

Try it online in the CJam interpreter.

### Output

```
{ _
 p }
{ _
 p }

```

### How it works

* `L` pushes an empty array and `~` dumps it. The stack is empty again.
* The block

```
{ _
 p }

```

pushes that block on the stack.
* `_` pushes a copy of the block and `~` executes the copy.

The `_` inside the copy of the block will push a copy of the original block, which `p` will print, followed by a linefeed.
* Finally, the interpreter prints the remaining item on the stack: the original code block.

# Answer
> 108 votes
# Perl, 7×7 (42 non-spaces)

```
for$i(
1..56 )
{$_= $i
%8? $i%
7? $":7
: $/;1;
 print}

```

## Output:

```
      7
     7
    7
   7
  7
 7
7

```

# Answer
> 77 votes
# CJam, 4X4 (~~12~~ 10 non-spaces)

```
 6,
SS +
* 4/
 N*

```

Output:

```
0  1
  2
 3
4  5

```

---

Previous version with 12 non-spaces:

```
 4a4
* 4S
** 4
/N*

```

And the output is

```
4
 4
  4
   4

```

As pointed out by Martin, this version has

* **4** Spaces,
* **4** `*`,
* **4** `4`,
* **4** other characters, and
* **4** `4` as the output

;)

Try it online here

# Answer
> 51 votes
# Marbelous - 16x16

```
....@0..@1....
@3..0A08..@2  ..
/\--....>1  ..Hp
..@2..\\  =0@3..
ss..//  --\\\\..
@0/\  @1/\Hp..!!
:s  #the-cake-is
  2020#a-pie/lie

```

Test it here! Spaces as blanks, cylindrical board, and include libraries all must be checked.

### Output

```
              07
            06
          05
        04
      03
    02
  01
01

```

### Explanation

There are two boards here: the main board (shown below), and the `ss` board, which takes no inputs and outputs two spaces (0x20) to STDOUT.

A blank cell is equivalent to a `..`, and anything after a `#` is a comment.

Every tick, `ss` outputs two spaces to STDOUT.

The green path is a simple loop that outputs a newline (0x0A) at the end of every 7th tick.

The blue path will output the numbers (`Hp` prints a marble as two hex digits) present in the output, at the end of every 6th tick.

After we have printed `01` once, the loop ends, and moves down the red path, which duplicates this marble.

One duplicate is printed (the second `01`), and the other is sent down the black path, which terminates the board at the `!!` cell. Because of the location of the `Hp` used in this last print, the `01` appears *before* the same tick's two spaces, rather than after, the behavior of every other `Hp` call.

# Answer
> 37 votes
# Python - 11x11

```
import re
[print(
    re.sub(
"0",   " ",
bin(x)[
2:].zfill(
11)))for x
in[19,15,
1920,116,
15,1,5,3,
3,3, 67]]

```

## Output

```
      1  11
       1111
1111
    111 1
       1111
          1
        1 1
         11
         11
         11
    1    11

```

It's a pretty messy and boring solution, but I just thought I'd show that...

1. It can be done in Python
2. If you can compress information about your code shorter than your code, then you can pull off something like this :)

This solution takes advantage of the fact that, if you're within a pair of brackets in Python, then you can split your code over several lines and arbitrarily add spaces without getting an `IndentationError`. Another way of doing something like this is by ending the line with a backslash.

# Answer
> 34 votes
# Python - 7x7 (37 non-spaces)

```
print(
'%+7s'
'\n'%1
*6+'%'
'-7s'%
111111
      )

```

## Output

```
      1
      1
      1
      1
      1
      1
111111

```

Uses Python's old `%` string formatting operator to do the job: `+7` and `-7` take care of right/left justification, and the last space to match the closing parenthesis for `print` in particular. In preparing the format string, we also have

* automatic concatenation of string literals across lines, and
* string repetition by multiplication (giving us multiple replacement fields for the price of one)

# Answer
> 18 votes
# JavaScript (9x9)

```
 i=9;q=""
; for(;++
i< 91;){;
var q=q+(
!(i% 10.0
)?1:" ");
;i%9|| (q
+="\n") }
alert(q)

```

# Output

```
1
 1
  1
   1
    1
     1
      1
       1
        1

```

# Notes

I made and golfed (to the best of my ability) code for a square with diagonal of any size n:

```
q="";for(i=***n***;++i<***n^2+n+1***;i%***n***||(q+="\n"))q+=i%***n+1***?"0":1

```

replacing the \***asdf\*** numbers with constants depending on the side length n, for example for n=6:

```
q="";for(i=6;++i<43;i%6||(q+="\n"))q+=i%7?" ":1

```

But, even though that code is length 46, I couldn't get the constant space to line up with a space in the diagonal of the code until it was as big as a 9x9, with a wasted line (the 5th one)

Edit: Changed to add alert(). Before:

```
 i=9;q=""
; while((
++ i)<91)
{q= q+""+
""+( "")+
(!((i %10
))?1:" ")
;i%9||( q
+="\n")}

```

# Answer
> 16 votes
# CJam, 5x5, 12 non-spaces

Not a winner, but I wanted to add a rather small and *sparse* submission, since most answers just print a diagonal.

```
 1 ]
D * S
 * 5
/ N *
 1 ;

```

prints

```
1 1 1
 1 1
1 1 1
 1 1
1 1 1

```

Test it here.

The last two characters of the code, don't do anything, so it actually only has 10 bytes of real code. For a smaller grid, I could even reduce it by another two bytes to 8, but that doesn't fit on 3x3, and this code doesn't work for even grid sizes.

How it works:

```
1]           "Push [1].";
  D*         "Repeat 13 times.";
    S*       "Riffle with spaces.";
      5/     "Split into runs of five elements.";
        N*   "Join those with line breaks.";
          1; "Push and pop a 1. No-op.";

```

# Answer
> 14 votes
# Befunge, 9x9

I have no idea why I did this. It took *way* too long. I have a massive headache now.

```
8>v_20gv
v9<^v#<4
1@,/<>^6
v1,*$:<p
->,!-^87
:^*25<^g
_88g,^^4
9vp\v#6<
        @

```

Output:

```
        @
        @
        @
        @
        @
        @
        @
        @
$$$$$$$$

```

## Some explanation

The code uses `g` to read the `@` characters from the grid "on the fly" (and also the final space, which is `@ / 2`), and `p` to modify the loop to write the last output line.

Every single character on the code is used at some point, either as code or as data (the `9` and the `@` on the two last lines).

I basically had to do a lot of workarounds to make the code work. The instruction pointer does multiple intersections during execution, of which some are jumped over. (I couldn't use any instruction there for different directions as they would interfere. There is no NOP.) Elsewhere I either reused the same character or just undid it (see the `$:` in the middle).

I also did some creative work on the stack:

* When the (inner) character writing loop terminates (all spaces done for this line), the stack has `n,0`. I then have to decrement `n`. The obvious solution would be `$1-`, but I managed to shorten it by using `!-`.
* When the (outer) line writing loop terminates (all normal lines printed), the stack has a `0`. I then organized code changer (`20g46p7g46\p`) to use that `0`, instead of wasting 2 characters on `$0`.

# Answer
> 13 votes
## Python 3, 8x8

There are 50 non-space characters and 14 spaces. The last line has one useless character, but everything else is necessary.

```
(*_,q,n
)=p='''
       p
'''[2:]
print(p
*2+q*7,
n+p*4+p
[0:-1])

```

Output:

```
       p
       p
ppppppp
       p
       p
       p
       p
       p

```

# Answer
> 12 votes
# Ruby, 8x8

```
 (0...8)
. map(){
|x |$><<
32. chr*
x+[x ]*'
'<<32 .\
chr*(7 -
x)+?\n}

```

Output:

```
0
 1
  2
   3
    4
     5
      6
       7

```

# Answer
> 9 votes
# CJam, 5X5

```
SSSS
1N]4
*B11
    S

```

And the output is

```
    1
    1
    1
    1
1111

```

~~I was this close to 4X4 solution. `<sigh>`~~ See my other answer

Try it online here

# Answer
> 9 votes
# C++, 12x12

**Edit:** So, I became a little obsessed with this challenge and managed to get it down from 17x17 to 12x12. It took me a little while to realize I could use `/**/` as a token delimiter. This code takes advantage of the fact that a line splice still works in Clang with a space after it, though it does give warnings and ruins Xcode's colorization of the code.

```
#include<c\
stdio>/***/
int/**/mai\
n(){for(in\
t/**/i=0;i\
<12;++i)pr\
intf(i^8?"\
           \
|\n":"~~~~\
~~~~~~~\x2\
0\n");}/**/

```

Output:

```
           |
           |
           |
           |
           |
           |
           |
           |
~~~~~~~~~~~
           |
           |
           |

```

# Answer
> 7 votes
# 05AB1E, 3x3 (6 non-space bytes)

```
 3Ð
Λ q
°°

```

**Output:**

```
3
 3
  3

```

Try it online.

**Explanation:**

```
3Ð       # Push three 3s to the stack
  Λ      # Canvas with parameters num; filler; pattern
         #  num: The amount of characters to display (3)
         #  filler: The character to display ('3')
         #  pattern: The available options are single-digit integers in the range [0,7]
         #           indicating the direction to print in.
         #           (Option 3 is a top-left to bottom-right diagonal line)
    q    # Exit the program
°°       # no-ops to complete the pattern

```

# Answer
> 6 votes
# Befunge-98, 8x8 (56 non-spaces \[11 nops\])

Note: In the interest of good sports-person-ship, this reads its own source via `'`, making it a cheat-quine to some. Read the debate here.

## Program

```
 07'?>:8v
v y+da:%<
<v ':vj!-
,+# '<zzv
v1#a vj!<
>z,\1 -\v
z>+,$v z<
1_@#:<v -
zzzzzv<z

```

## Output

```
(
 ,
  &
   %
    $
     #
      "
       !

```

## Explanation

The un-golfed version

```
07'?>:8%:ad+y-!jv>'n,$v
  !jv   a,\1-\v > 's,
    >         >       v
    v-1_@#:           <

```

(non-space and space are replaced with 'n and 's for readability sake.)

This solution is based off of the fact that using an index \[0,width^2) mod the width of the square can tell you if you are at the end of the row or on the diagonal. Since all spaces are placed along the diagonal, it is easy to tell when to print a non-space!

### In Pseudocode

```
const int WIDTH = 8
push 0    //Because of the way the 'y' instruction works when picking
int row=7 //8-1 rows
int i=63  //Starting at the end allows for the cheaper i != 0
do
{
    pick variable row from the stack bottom + 1//ad+y
    if(i%WIDTH == row)
    {
        print non-space
    }
    else
    {
        print space
        if(i%WIDTH == 0)
        {
            print new-line
            --row
        }
    }
  --i
}
while(i != 0);

```

## Discussion

I'm very proud of it, though I wish I could have made every non-space also a non-nop. I'm also proud that I didn't use the standard Befunge get-increment-put trope! It prints out different symbols for non-space because I had the room for it and didn't want to be boring.

Try it on Windows with BefungeSharp!

# Answer
> 4 votes
# CJam, 4 x 4 (8 non-spaces)

```
 N a
` S
 * N
X $

```

Try it online in the CJam interpreter.

### Output

```
[ "
 " ]
[ "
 " ]

```

### How it works

* `N` pushes a linefeed as a singleton string. `a` wraps that string in an array.
* ``` inspects the result, i.e., it pushes a string representation of the array.

This is the result:

```
["
"]

```
* `S*` joins the resulting string (array of characters), separating its elements using spaces. In other words, it puts a space character between all pairs of adjacent characters of the string.

This is the result:

```
[ "
 " ]

```
* `N` pushes another linefeed.
* `X$` copies the stack item at index 1 (counting from the top), i.e., the multi-line string.
* Finally, the interpreter prints all items on the stack: the original multi-line string, the linefeed and the copy of the multi-line string.

# Answer
> 4 votes
# SOGL V0.12, 2x2 (2 non-spaces)

```
2
 ╚

```

Try it Here!

### Output

```
 /
/

```

### Explanation

In SOGL all lines except the last are replacing lines - it replaces everywhere in the continuing code the last character of the line with everything before it. SO the 1st line here is `replace space with 2 in the next line`.
Then the next line - `2╚` gets executed: `2` pushes 2, and  creates a diagonal of size 2.

# Answer
> 3 votes
# CBM BASIC v2.0 (8×8)

An improvement over my previous answer, using a completely different approach:

```
1s=56/8
2?sP7);
3?"?"::
4s=s-+1
5ifsgO2
6?-8^6;
7?sP1):
       8

```

Output:

```
       ?
       ?
       ?
       ?
       ?
       ?
       ?
-262144

```

# Answer
> 3 votes
## Ruby, ~~8x8~~ 7x7

```
 print(
 (?f+"\
 "*6+?\
 )*6).!
 $><<"\
 f"<<!1
;

```

Output:

```
f
f
f
f
f
f
 ffalse

```

Previous version, 8x8 with 20 spaces:

```
  puts((
  "ff"+#
  ?\s*6+
  ?\n)*7
  );$><<
  ?\s*2+
  ?f;p:p
.!

```

Output:

```
ff
ff
ff
ff
ff
ff
ff
  ffalse

```

# Answer
> 3 votes
# Pushy, 4x4 square

Non-competing as the language postdates the challenge:

**Code:**

```
 H32
2 C4
:" }
\o/

```

**Outputs:**

```
d
 d
  d
   d

```

**Try it online!**

Because whitespace is irrelevant in Pushy, the code is easily arranged to match the negative of its output. The actual program looks like this:

```
H      \ Push char 100, 'd'
32 2C  \ Push char 32, a space, and make 2 extra copies
       \ We now have the string 'd   '
4:     \ 4 times do:
  "    \   Print the string
   }   \   Cyclically shift it right, once

```

Backslashes begin a comment, so the trailing `\o/` is just there to complete the negative, and look cool.

---

Alternatively, for the same score, we can have the following solutions:

```
Code    Output

 35;    #
3 2j     #
2C 4      #
:"}        #

K 36     #
33 2      #
Ct4        #
 :}"    #

```

# Answer
> 3 votes
# Haskell, 10 × 10

```
main=let{
0&c='\32'
!c;n&c=c!
'\32'>>(n
-1)&c;a!b
=putStrLn
$(b<$[1..
10])++[a]
}in(9&'*'
         )

```

Defines a helper function `a ! b` that prints a line of the form `bbbbbbbbba`, and a recursive function `n & c` that prints `n` lines of the form `ccccccccc␣` followed by one line of the form `␣␣␣␣␣␣␣␣␣c`.

Uses `<$` (`fmap const`, again) on a range to repeat a character. Note that `<$` is only available without imports since GHC 7.10, which post-dates this challenge. ~~I am not entirely sure if this makes this submission noncompeting.~~

Nothing really exciting with the choice of layout or algorithm here; I didn't have a lot of bytes to spare and it's just fortunate one can get the line breaks to occur around the `putStrLn` the way they did.

# Answer
> 3 votes
# Vyxal `j`, 3x3 square

```
 3ƛ
S ↳
3↲

```

Try it Online!

# Answer
> 2 votes
## Perl, 6x6 (26 non-spaces)

I spent a whlie looking through these and was sure there would be a Perl solution smaller than 7x7 somehow... A very fun challenge! This solution requires `-E`.

```
say+(
$"x5,
"5$/"
)x5,5
x5,$"
     ;

```

### Usage:

```
perl -E 'say+(
$"x5,
"5\n"
)x5,5
x5,$"
     ;'

```

### Output:

```
     5
     5
     5
     5
     5
55555

```

# Answer
> 2 votes
# CBM BASIC v2.0 (9×9)

```
0dA8,7,6
1dA5,4, 3
2dA2,1 ,0
3rEs: rem
4?sP s)::
5:? "*";:
6p =8---s
7 ?sPp):?
 8ifsgO3:

```

Output:

```
        *
       *
      *
     *
    *
   *
  *
 *
*

```

# Answer
> 2 votes
# Jelly, 4 x 4 (12 non-spaces)

```
 4=þ
¢ +⁴
¢+ ⁴
¢ỌY

```

Try it online!

Output:

```
!
 !
  !
   !

```

This was pretty fun.

### How it works

```
 4=þ    Link 1 (nilad): Generate an identity matrix of size 4
¢ +⁴    Link 2 (nilad): Add 16 to above
¢+ ⁴    Link 3 (nilad): Add 16 again
¢ỌY     Main link (nilad): Convert the above to ASCII chars, and join by newline

```

Easy part: Jelly ignores whitespaces (as long as only one-byte builtins are used).

Hard part: Each line in Jelly is a separate link (or function), so it's not very short to spread a constant statement in multiple lines. Using a string literal is a good candidate, but no idea how to generate the negative.

# Answer
> 1 votes
# C (gcc), ~~7x7~~ 8x8

EDIT: Previous version had incorrect behaviour.

```
 main(i)
{ for(;i
<9 ;pri\
ntf ("%\
*d%" "*\
c",i, 1,
9-i,10 )
,i++);}

```

Try it online!

# Answer
> 1 votes
# PHP, 11 x 11 square

```
 for($x=0;#
 $x<10;$x++
 ){echo('|'
 .#########
 str_repeat
 (chr(32),#
 10)."\n");
 }echo(chr(
 32).'----'
 .'------')
;

```

Output:

```
|
|
|
|
|
|
|
|
|
|
 ----------

```

This was a nightmare. I don't think I can fit any smaller.

Try it online!

# Answer
> 1 votes
# JavaScript (SpiderMonkey), 71 bytes

```
for(i=s
='';71 >
++i;s +=
i%9? i%+
8?' ':+1
:[ '\n']
) ;print
 (s);;;;

```

Try it online!

Why everyone do LU-RD diag?

# Answer
> 1 votes
# brainfuck, 15x15, 112 nonspace

```
 + + + + + + +
+ [ - > + > + +
 + + + + + + +
+ + + < < ] > +
 + > > + > > +
< < [ < . [ - >
 > + < < ] > >
[ - < < + + + >
 > ] > + + + +
+ + + + + + + +
 + + + + + [ <
] < < < < [ . >
 > + + > > + <
< < < < ] > > >
 + ] a a a a a

```

Try it online!

```
++++++++[->+>++++<<]>++>>+>>+<<[    10 32(00)00 01 ; Old didn't care nonspaces
<.[->>+<<]>>[-<<+++>>]>             10 96 01 00(01)       10 96 16 0(-17)
+++++++++++++++++[<]<<<<        (00)10 96 01 00 18       (10)96 16 00 00
[.>>++>>+<<<<<]>>>+]                10 96(02)00 18        10 96(18)00 01

```

# Answer
> 0 votes
# Deadfish~, 10x10 square

```
 {(icdcccc
 ccccc{dd}
 ddc{d}){i
 ii}ii}cic
 cccccccch
 hhhhhhhhh
 hhhhhhhhh
 hhhhhhhhh
 hhhhhhhhh
h

```

Outputs

```
!
!
!
!
!
!
!
!
!
 !!!!!!!!!

```

# Explanation

```
{           repeat 10 times
(           skip following the first time (if accumulator is 0), so repeat x9
ic          increment (will be 32 once this is run , so 33, then print as '!'
dccccccccc  decrement (to 32) and print 9 times
{dd}dd      decrement to 10 for newline
c{d}        print and decrement to 0
)           end if
{iii}ii     increment accumulator to 32
}           end loop
c           print as character (' ')
iccccccccc  increment and print 9 '!'s
h           stop the program, anything after this is junk

```

Try it online!

---
Tags: code-golf, quine, source-layout, whitespace
---


title: The Lucas-nacci Numbers

text:
# Question
Title: The Lucas-nacci Numbers
## Background

Most everyone is familiar with the *Fibonacci numbers* \\$F(n)\\$:

> \\$0, 1, 1, 2, 3, 5, 8, 13, 21, ...\\$

These are formed by the recursion function \\$F(n) = F(n-1) + F(n-2)\\$ with \\$F(0)=0\\$ and \\$F(1)=1\\$. A000045

A closely related sequence is the *Lucas numbers* \\$L(m)\\$:

> \\$2, 1, 3, 4, 7, 11, 18, 29, ...\\$

These are formed by the recursion function \\$L(m) = L(m-1) + L(m-2)\\$ with \\$L(0)=2\\$ and \\$L(1)=1\\$. A000032

We can alternate between the two sequences based on even/odd indices, with the construction

$$A(x) = \begin{cases} F(x) & x \equiv 0 \pmod 2 \\ L(x) & x \equiv 1 \pmod 2 \\ \end{cases}$$

For example, \\$A(4)\\$ is equal to \\$F(4)\\$ since \\$4 \bmod 2 \equiv 0\\$. We'll call this sequence the *Lucas-nacci Numbers*, \\$A(x)\\$:

> 0, 1, 1, 4, 3, 11, 8, 29, 21, 76 ...

This can be formed by the recursion function \\$A(x) = 3A(x-2) - A(x-4)\\$ with \\$A(0)=0, A(1)=1, A(2)=1\\$, and \\$A(3)=4\\$. A005013

## Challenge

Given input \\$n\\$, output the sequence of \\$n+1\\$ numbers up to and including \\$A(n)\\$ as described above. Fewest bytes (or byte-equivalents, such as for LabVIEW, as determined individually on Meta) wins.

## Input

A single non-negative integer \\$n\\$.

## Output

A list of numbers that correspond to the subsequence of Lucas-nacci numbers from \\$A(0)\\$ to \\$A(n)\\$. The list must be in sequential order as described above.

## Rules

* Standard code-golf rules and loophole restrictions apply.
* Standard input/output rules apply.
* Input number can be in any suitable format: unary or decimal, read from STDIN, function or command-line argument, etc. - your choice.
* Output can be printed to STDOUT or returned as a result of the function call. If printed, suitable delimiters to differentiate the numbers must be included (space-separated, comma-separated, etc.).
* Additionally, if output to STDOUT, surrounding whitespace, trailing newline, etc. are all optional.
* If the input is a non-integer or a negative integer, the program can do anything or nothing, as behavior is undefined.

## Examples

```
Input -> Output
0 -> 0
5 -> 0, 1, 1, 4, 3, 11
18 -> 0, 1, 1, 4, 3, 11, 8, 29, 21, 76, 55, 199, 144, 521, 377, 1364, 987, 3571, 2584

```

# Answer
> 9 votes
# Jelly, 12 bytes

```
;2U+¥Ð¡-,1ZḢ

```

Try it online!

### Background

We can extend F and L to -1 by defining F(-1) = 1 and L(-1) = -1. This is consistent with the recursive function.

Our program starts with

```
-1  1
 0  2

```

In each step, to form the next pair, we reverse the last pair and add it to the penultimate pair. For example:

```
[0, 2] U+¥ [-1, 1] -> [2, 0] + [-1, 1] -> [1, 1]

```

If we continue this process for a few more steps, we get

```
-1  1
 0  2
 1  1
 1  3
 4  2
 3  7
11  5

```

The Lucas-nacci sequence is simply the left column.

### How it works

```
;2U+¥Ð¡-,1ZḢ  Niladic link. No implicit input.
              Since the link doesn't start with a nilad, the argument 0 is used.

;2            Concatenate the argument with 2, yielding [0, 2].
       -,1    Yield [-1, 1]. This is [L(-1), F(-1)].
    ¥         Create a dyadic chain of the two atoms to the left:
  U             Reverse the left argument.
   +            Add the reversed left argument and the right one, element-wise.
     Ð¡       For reasons‡, read a number n from STDIN.
              Repeatedly call the dyadic link U+¥, updating the right argument with
              the value of the left one, and the left one with the return value.
              Collect all intermediate results.
          Z   Zip the list of results, grouping the first and seconds coordinates.
           Ḣ  Head; select the list of first coordinates.

```

`Ð¡` peeks at the two links to the left: `2` and `U+¥`. Since the leftmost one is a nilad, it cannot be the body of the loop. Therefore, `U+¥` is used as body and a number is read from input. Since there are no command-line arguments, that number is read from STDIN.

# Answer
> 6 votes
# Haskell, ~~59~~, ~~57~~, ~~56~~, ~~52~~, 51 bytes

```
l a=2*mod a 2:scanl(+)1(l a)
f n=[l i!!i|i<-[0..n]]

```

Series definition adapted from this answer.

Less golfed:

```
fibLike start = start : scanl (+) 1 (fibLike start)
whichStart i = (2*mod i 2)
lucasNacci i = fibLike (whichStart i) !! i
firstN n = [ lucasNacci i | i <- [0..n]]

```

`fibLike start` gives an infinite list, defined: `f(0)=start, f(1)=1, f(n)=f(n-1) + f(n-2)`. `whichStart i` returns 2 for odd input (Lucas series) or 0 for even (Fibonacci series). `lucasNacci i` gives the ith Lucas-nacci number. `firstN n` maps over the list.

One byte saved by Boomerang.

# Answer
> 6 votes
## CJam, ~~21~~ 20 bytes

*Thanks to Sp3000 for saving 1 byte.*

```
TXX4ri{1$3*4$-}*?;]p

```

Test it here.

### Explanation

Simply uses the recurrence given in the challenge spec.

```
TXX4 e# Push 0 1 1 4 as base cases.
ri   e# Read input and convert to integer N.
{    e# Run this N times...
  1$ e#   Copy a(n-2).
  3* e#   Multiply by 3.
  4$ e#   Copy a(n-4).
  -  e#   Subtract.
}*
?;   e# Discard the last three values, using a ternary operation and popping the result.
]p   e# Wrap the rest in an array and pretty-print it.

```

# Answer
> 6 votes
# Perl 6, 42 bytes

```
{(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}

```

**usage**

```
> my &f = {(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}
-> ;; $_? is raw { #`(Block|184122176) ... }
> f(0)
(0)
> f(5)
(0 1 1 4 3 11)
> f(18)
(0 1 1 4 3 11 8 29 21 76 55 199 144 521 377 1364 987 3571 2584)

```

# Answer
> 5 votes
## ES6, 65 bytes

```
n=>[...Array(n)].map(_=>a.shift(a.push(a[2]*3-a[0])),a=[0,1,1,4])

```

Uses the recurrence relation given in the question.

# Answer
> 5 votes
# Oracle SQL 11.2, ~~218~~ ~~216~~ 201 bytes

```
WITH v(a,b,c,d,i)AS(SELECT 0,1,1,4,3 FROM DUAL UNION ALL SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1)SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4UNION ALL SELECT d FROM v WHERE:1>2;

```

Un-golfed

```
WITH v(a,b,c,d,i) AS
(
  SELECT 0,1,1,4,3 FROM DUAL
  UNION ALL
  SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1
)
SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4
UNION ALL SELECT d FROM v WHERE:1>2;

```

I managed to gain a few bytes by using (abusing ?) the SIGN function to generate the first 3 elements of the sequence.

# Answer
> 5 votes
## Retina, ~~70~~ ~~62~~ 59 bytes

```
1
¶$`1
m`^(11)*1$
$&ff
m`$
 f
+`1(f*) (f*)
$2 $2$1
 f*

f
1

```

Try it online

* Input is in unary base, *n* 1s.
* `1?` `$`¶` \- Create a line for each number from 0 to *n*: `, 1, 11, 111, 1111, ...`
* `m`^(11)*1$` `$&ff` \- Append `ff` to odd lines. This will seed the function with L(0)=2.
* `m`$` `f` \- Append `f` to all lines (note the space). This seeds the function with 0 and 1 for Fibonacci numbers, and 2 and 1 for Lucas numbers.
* `+`1(f*) (f*)` `$2 $2$1` \- Loop: calculate F(n+1) = F(n) + F(n-1) while there are still 1s.
* `f*`  \- Remove F(n+1) from the end of each line.
* Replace `f`s back to 1s. If this isn't needed and we can stay with `f`s, the length is just 55 bytes.

# Answer
> 3 votes
# Japt, ~~25~~ ~~22~~ 21 bytes

```
Uò £MgXf2)+X%2*Mg°X)r

```

Test it online!

### Background

It's somewhat difficult to create a Fibonacci sequence in Japt, but we have a built-in `Mg` to do it for us. However, this only gives us the Fibonacci sequence, not the Lucas sequence. We can accomplish the Lucas sequence fairly easily using this trick:

```
N    F(N-1)  F(N+1)  F(N-1)+F(N+1)
0    1       1       2
1    0       1       1
2    1       2       3
3    1       3       4
4    2       5       7
5    3       8       11
6    5       13      18
7    8       21      29

```

As you can see, `F(N-1) + F(N+1)` is equal to `L(N)` for all `N`. However, since we only need Lucas numbers on the odd indices, we can combine the two formulas into one:

```
N    N-N%2  N+N%2    F(N-N%2)  F(N+N%2)*(N%2)  F(N-N%2)+F(N+N%2)*(N%2)
0    0      0        0         0               0
1    0      2        0         1               1
2    2      2        1         0               1
3    2      4        1         3               4
4    4      4        3         0               3
5    4      6        3         8               11
6    6      6        8         0               8
7    6      8        8         21              29

```

### How it works

```
Uò £  MgX-1 +X%2*Mg° X)r
Uò mX{MgX-1 +X%2*Mg++X)r

             // Implicit: U = input integer
Uò mX{       // Create the inclusive range [0..U], and map each item X to:
MgXf2)+      //  Floor X to a multiple of 2, calculate this Fibonacci number, and add:
+X%2*Mg++X)  //  Calculate the (X+1)th Fibonacci number and multiply by X%2.
)r           //  Round the result. (The built-in Fibonacci function returns
             //  a decimal number on higher inputs.)

```

# Answer
> 3 votes
# Mathematica, ~~52~~ 51 bytes

```
If[#>2,3#0[#-2]-#0[#-4],#-If[#>1,1,0]]&/@0~Range~#&

```

Very similar idea to Martin's above, I spent some time trying to find a shorter way of defining the "base cases" for the function. Polynomial interpolation was a bust, so I went for this, using the extension into negatives to yield a fairly short definition.

# Answer
> 2 votes
# Brachylog, 51 bytes

```
:0re{:4<:[0:1:1:4]rm!.|-4=:1&I,?-2=:1&*3-I=.}w,@Sw\

```

This takes a number as input and prints to STDOUT the list, with spaces separating each number.

### Explanation

```
§ Main predicate

:0re{...}               § Enumerate integers between 0 and the Input, pass the integer
                        § as input to sub-predicate 1
         w,@Sw          § Write sub-predicate 1's output, then write a space
              \         § Backtrack (i.e. take the next integer in the enumeration)

§ Sub-predicate 1

:4<                     § If the input is less than 4
   :[0:1:1:4]rm!.       § Then return the integer in the list [0,1,1,4] at index Input

|                       § Else

-4=:1&I,                § I = sub_predicate_1(Input - 4)
        ?-2=:1&*3-I=.   § Output = sub_predicate_1(Input - 2) * 3 - I

```

The cut `!` in the first rule of sub-predicate 1 is necessary so that when we backtrack (`\`), we don't end up in an infinite loop where the interpreter will try the second rule for an input less than 4.

# Answer
> 2 votes
# MATL, 17 ~~18~~ bytes

```
0ll4i:"y3*5$y-](x

```

Almost direct translation of Martin's CJam answer.

**Try it online!**

```
0ll4       % push first four numbers: 0,1,1,4
i:         % input n and generate array [1,2,...,n]
"          % for loop. Repeat n times
  y        % copy second-top element from stack
  3*       % multiply by 3
  5$y      % copy fifth-top element from stack
  -        % subtract. This is the next number in the sequence
]          % end loop
(x         % indexing operation and delete. This gets rid of top three numbers

```

# Answer
> 2 votes
## Mathematica, 56 bytes

```
f@0=0
f@1=f@2=1
f@3=4
f@n_:=3f[n-2]-f[n-4];
f/@0~Range~#&

```

Very straightforward implementation. Defines a helper-function `f` and then evaluates to an unnamed function which applies `f` to a range to get all the results. This feels unnecessarily cumbersome.

A single unnamed function seems to be one byte longer though:

```
Switch[#,0,0,1,1,2,1,3,4,_,3#0[#-2]-#0[#-4]]&/@0~Range~#&

```

# Answer
> 2 votes
# , 55 bytes

```
A=c(0,1,1,4);for(x in 4:scan()+1)A[x]=3*A[x-2]-A[x-4];A

```

Try it online!

* -24 bytes thanks to JayCe

# Answer
> 2 votes
# Mathematica, 41 bytes

```
LinearRecurrence[{0,3,0,-1},{0,1,1,4},#]&

```

# Answer
> 2 votes
# Groovy, 50 Bytes

```
x={a,b=0,c=1,d=1,e=4->a<0?:[b,x(a-1,c,d,e,3*d-b)]}

```

This defines the function x, which takes in n as it's first argument and has the base case of the first four numbers in the Fibocas sequence as default arguments for the rest of the function.

a here is n. b, c, d, and e are the next four elements in the sequence.

It decrements n and recurses until n is less than zero-- when it recurses, it adds on to the ultimate return value the first element in its current sequence. The new values for the next four elements in the sequence are given to the recursive call-- the last three elements are shifted over to be the first three, and a new fourth element is generated from two of the previous elements using 3\*d-b.

It delimits new values with list nestings, as groovy can return multiple values by stuffing them into a list-- so each call returns the current first element and the result of recursion, which will be its own list.

# Answer
> 2 votes
# C++ Template Meta Programming, 130 bytes

```
template<int X>struct L{enum{v=3*L<X-2>::v-L<X-4>::v};};
#define D(X,A) template<>struct L<X>{enum{v=A};};
D(0,0)D(1,1)D(2,1)D(3,4)

```

Recursive definitions somehow cry for C++TMP, usage:

```
L<x>::v

```

with `x` being the `A(x)` you like.

# Answer
> 1 votes
# Pylons, 19

This is a pretty direct translation of Martin's approach.

```
0114{@-4@-33*-,i}=4

```

How it works:

```
0114    # Push 0, 1, 1, 4 to the stack.
{       # Start a for loop.
 @-4    # Get the stack element at index -4
 @-3    # Get the stack element at index -3
 3      # Push 3 to the stack.
 *      # Multiply the top two elements of the stack.
 -      # Subtract the top two elements of the stack.
  ,     # Switch to loop iterations.
 i      # Get command line args.
}       # End for loop.
=4      # Discard the top 4 elements of the stack.

```

# Answer
> 1 votes
# DUP, 32 bytes

```
[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]

```

`Try it here!`

An anonymous lambda that leaves a sequence of numbers on the stack. Usage:

```
8[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]!

```

# Explanation

```
[                              {start lambda}
 a:                            {save input number to a}
   0 1$4                       {base cases to get us started}
        [       ][       ]#    {while loop}
         a;1-$a:               {a--, check if a>0}
                  1ø3*4ø-      {3*stack[n-2]-stack[n-4]}

                           %%  {discard top 2 stack items}
                             ] {end lambda}

```

# Answer
> 1 votes
## Python 2, 71 bytes

```
def a(n,x=0,y=1,z=2,w=1,p=0):
 if~n:print[x,z][p];a(n-1,y,x+y,w,z+w,~p)

```

This definitely seems too long. However, I was pleased that I got to use the bitwise `not` operator...twice. Once as kind of a parity flip back and forth, and once to terminate the recursion when `n` reaches `-1`.

The variable `p` will always be either `0` or `-1`, so it will alternate between entries `0` or `-1` of the list. (Choosing entry `-1` of a Python list means choosing the last element.)

# Answer
> 0 votes
# Jelly, 8 bytes

```
ŻÆĿÆḞḂ?€

```

Try it online!

Close to a literal interpretation of the spec

## How it works

```
ŻÆĿÆḞḂ?€ - Main link. Takes N on the left
Ż        - Range from 0 to N
       € - Over each integer k:
      ?  -   If:
     Ḃ   -     Condition: k mod 2
 ÆĿ      -     Truthy: kth Lucas number
   ÆḞ    -     Falsey: kth Fibonacii number

```

---
Tags: code-golf, math, sequence
---


title: Write a binary counter in quine

text:
# Question
Title: Write a binary counter in quine
Write two code fragments, which we will call s\_zero and s\_one.

Program (l, n) consists of l copies of s\_zero and s\_one corresponding with the digits of n in binary, padded with s\_zero on the left.

For example, if s\_zero = `foo` and s\_one = `bar` then
Program (4, 0) = `foofoofoofoo`
Program (4, 1) = `foofoofoobar`
Program (4, 2) = `foofoobarfoo`
etc.

Program (l, n) must print the source of Program (l, (n + 1) mod (2^l)) to standard out. In the example above, `foobarfoofoo` must print `foobarfoobar` when executed.

Your score is the sum of the lengths of fragments s\_zero and s\_one

# Answer
> 6 votes
# CJam, 29 + 29 = 58 bytes

The 0 code:

```
0{"_~"]]z(3\+2b(2b2>a\+z~[}_~

```

The 1 code:

```
1{"_~"]]z(3\+2b(2b2>a\+z~[}_~

```

### Explanation

```
0                       " Push the current bit. ";
{"_~"                   " The basic quine structure. ";
    ]                   " Make an array of the current bit, the function and _~.
                          That is the code fragment itself. ";
    ]                   " Make an array of all code fragments in the stack. ";
    z(                  " Extract the array of the bits. ";
    3\+2b(2b2>          " Convert from base 2, decrease by one and convert back,
                          keeping the length. ";
    a\+z                " Put the bits back to the original position. ";
    ~                   " Dump the array of code fragments back into the stack. ";
    [                   " Mark the beginning position of the array of the next code fragment. ";
}_~

```

# Answer
> 3 votes
# CJam, 47 + 47 = 94 bytes

The 0 code:

```
{`"_~"+]:+T2*0+:T)\AsSerS/_,(@2Y$#+2bU@->]zs}_~

```

The 1 code:

```
{`"_~"+]:+T2*1+:T)\AsSerS/_,(@2Y$#+2bU@->]zs}_~

```

Excuse the expletive.

I'm sure I can still shave off a few bytes there. I'll add an explanation once I decide that I can't be bothered to golf it any further.

Test it here.

# Answer
> 3 votes
# Python 3.8 (pre-release), ~~264 250~~ 120 + 120 = 240 bytes

## Code 0: (120 bytes)

```
for i in(c:=[]),0:
 c+=0,;exec(s:="i or print(end=f'for i in(c:=[]),0:\\n c+={c[0]^all(c:=c[1:-1])},;exec(s:=%r)#'%s)")#

```

Try it online!

## Code 1: (120 bytes)

```
for i in(c:=[]),0:
 c+=1,;exec(s:="i or print(end=f'for i in(c:=[]),0:\\n c+={c[0]^all(c:=c[1:-1])},;exec(s:=%r)#'%s)")#

```

Try it online!

## Test Suite

Try it online!

## How it works:

* `c` store the binary number of the program on the form of a list

The for loop execute twice :

* the first time, it assigns `c` to the correct value
* the second time, it prints the code replacing a char by 1 or 0 depending on `c`. The `n`th time `c[0]^all(c:=c[1:-1])` is called, it returns the `n`th leftmost bit of `c+1`

the next for loop are ignored thanks to the comment `#`

The printing is a derivate of this quine : `exec(s:="print('exec(s:=%r)'%s)")`

# Answer
> 1 votes
# CJam, 45 + 45 = 90 bytes

The **0** code:

```
{`]W=L0+:L,Ua*L2b)2b+L,W*>\f{X$!s/\s*"_~"}}_~

```

The **1** code:

```
{`]W=L1+:L,Ua*L2b)2b+L,W*>\f{X$!s/\s*"_~"}}_~

```

Explanation soon.

Try it online here

# Answer
> 1 votes
# GolfScript, 37 + 37 = 74 bytes

```
0{`".~"+:q;]-2%1\{1$^.@&q@}%\;-1%~}.~

```

```
1{`".~"+:q;]-2%1\{1$^.@&q@}%\;-1%~}.~

```

Not quite as short as user23013's CJam solution, but I figured I'd post this anyway, if only to (marginally) increase the diversity of the languages used.

My solution not directly based on any of the existing solutions (and, indeed, I haven't examined them in detail, as I still don't read CJam very well), but they all feature variants of the same basic quine structure (`{".~"}.~` in GolfScript, `{"_~"}_~` in CJam). That's not really very surprising, since it seems to be one of the most efficient ways to write a quine with an arbitrary payload in these languages.

There are several parts of this code I don't really like, and I suspect it may be possible to golf this further, but I've spent too much time on this as it is.

---
Tags: code-golf, quine, source-layout
---


title: The anti-narcissist

text:
# Question
Title: The anti-narcissist
The narcissist is a program which, given its own source as input, prints a truthy value and, given anything other than that, prints a falsey value. Today, we're reversing this.

Create a program that, given the name of whatever your language's truthy value is (True, true, 1), prints its own source. Given the name of whatever your language's falsey value is (False, false, 0), or any input other than these two, it should output nothing (empty string or array: erroring is acceptable).

Trailing whitespace is only good if your language needs it printed alongside with the code.

You need not account for all truthy and falsey values. You can choose one truthy and one falsey value for input.

For languages without truthy/falsey values, use 1 and 0.

This is code golf so the shortest program wins. Standard loopholes and quine rules apply.

# Answer
# Gol\>\<\>, 8 bytes

```
sP#;H?I"

```

Try it online!

Adapted from my comment on this answer.

### Explanation

```
sP        Pop and add 17 to the bottom of the stack (default 0)
  #       Reflect
sP        Add 17 again to make 34
       "  Wrapping string literal to push the source
     ?I   If the input is non-zero
    H     Halt and output the stack
   ;      Otherwise just halt

```
> 3 votes

# Answer
# Java 10, ~~227~~ 202 bytes (full program)

```
interface N{static void main(String[]a){var s="interface N{static void main(String[]a){var s=%c%s%1$c;if(new Boolean(a[0]))System.out.printf(s,34,s);}}";if(new Boolean(a[0]))System.out.printf(s,34,s);}}

```

-25 bytes thanks to *@ripkoops*.

Try it online.

# Java 10, 98 bytes (lambda function)

```
b->{var s="b->{var s=%c%s%1$c;return b?s.format(s,34,s):%1$c%1$c;}";return b?s.format(s,34,s):"";}

```

Try it online.

**explanation:**

* The `var s` contains the unformatted source code
* `%s` is used to put this String into itself with `s.format(...)`
* `%c`, `%1$c`, and `34` are used to format the double-quotes
* `s.format(s,34,s)` puts it all together

And then a ternary if-else check is added, which prints this source code if truthy, or an empty string if falsey.
> 3 votes

# Answer
# Vyxal, 10 bytes

```
`:qp*`:qp*

```

Try it True! Try it False!
> 2 votes

# Answer
# Python 2, 55 bytes

```
a=input();_='a=input();_=%r;print(_%%_*a)';print(_%_*a)

```

Try it online!

-10 bytes thanks to milkyway

Takes `1` or `0` as input. Technically you could give another integer but that produces weird behaviour.
> 1 votes

# Answer
## Haskell, 42 bytes

```
f n|n=putStr<>print$"f n|n=putStr<>print$"

```

Try it online!

A simple modification of the standard quine (current version of the Prelude with `<>` required). Throws an error when given `False`.
> 1 votes

# Answer
# Brachylog, 20 bytes

```
≜!1∧"≜!1∧~kgjw₁"gjw₁

```

Try it online!

Brachylog doesn't really have truthy or falsy *values*, so this just assumes that 0 and 1 are valid choices regardless of actual truthiness.

```
≜                       Label the input,
 !                      and discard the resulting choice point.
  1                     If the input is 1,
   ∧"≜!1∧~kgjw₁"gjw₁    quine.

```

This could be reduced to `1∧"1∧~kgjw₁"gjw₁` if we only had to handle the chosen values, or only integers, or only literals--`≜!` is necessary to handle an empty input or variable input. A lot of different two-byte chunks of code could work in place of `≜!`, such as any one of `023456789\^cxzạḅịḷṇụċṁṗẠḄḌẸḤỊḶṆṢṬṾẈẒĊĖṀȮṠṪπφ` followed by `|`, but `≜!` seems like the best for specifically catching an unbound input.
> 1 votes

# Answer
# Perl 5 (`-p`), ~~29~~ 24 bytes

Could save 2 bytes thanks to @Abigail, and some more thanks to this track

```
$_&&=<<''x2
$_&&=<<''x2

```

TIO
> 0 votes

# Answer
# 05AB1E, ~~21~~ 18 bytes

```
"34çìIΘ·×"34çìIΘ·×

```

-3 bytes thanks to *@Grimy*.

Try it online.

**Explanation:**

NOTE: Only `1` is truthy in 05AB1E. Everything else is falsey.

It's based on this base quine: `"34çìDJ"34çìDJ` (or to be more correct: `"34çì2×"34çì2×`)

```
"34çìIΘ·×"          # Push string "34çìIΘ·×"
          34ç       # Push 34, converted to character '"'
             ì      # Prepend it in front of the string: '"34çìIΘ·×'
              I     # Push the input
               Θ    # Trutify it (==1)
                ·   # Double it
                 ×  # And repeat the string that many times
                    #  with truthy input 1: '"34çìIΘ·×"34çìIΘ·×'
                    #  with falsey input: ""
                    # (after which the result is output implicitly)

```
> 0 votes

# Answer
# Pyth, 15 bytes

```
*QjN*2]"*QjN*2]

```

Try it online!

Input is either `True` or `False`. is a modification of the standard Pyth quine, `jN*2]"jN*2]`.

```
*QjN*2]"*QjN*2]   Implicit: Q=eval(input()), N=quote mark
       "*QjN*2]   The string "*QjN*2]" - closing quote is inferred
      ]           Wrap in a list
    *2            Duplicate
  jN              Join on "
*Q                Multiply by Q - True is evaluated to 1, False to 0
                  Implicit print

```

---

Technically, a truthy value in Pyth is any value not in the following list: `0, 0.0, "", [], (), {}, set()`, whereas my submission above only works with the strict values for `True` and `False`. If we need to cater for any truthy or falsey value, the following will work for **19 bytes**: `?!QkjN*2]"?!QkjN*2]` (TIO link). This replaces the multiplcation with `?!Qk`, which uses the negation of the truthiness of the input (`!Q`) to select either an empty string (`k`) or the quine string through the ternary operator (`?`).
> 0 votes

# Answer
# JavaScript (Node.js), 16 bytes

Assuming the only falsey string is the empty one

```
f=_=>_?'f='+f:''

```

Try it online!

---

# JavaScript (Node.js), 19 bytes

Assuming anything different from `true, false, 1, 0` is falsey

```
f=_=>~_+1?'f='+f:''

```

Try it online!
> 0 votes

# Answer
# Japt, 14 bytes

Based on ETH's original standard quine. Expects `0` for falsey and `1` for truthy.

```
"iQ pUÑ"iQ pUÑ

```

Try it

```
"iQ pUÑ"iQ pUÑ     :Implicit input of integer U
"iQ pUÑ"           :Literal string
        i          :Prepend
         Q         :  Quotation mark
           p       :Repeat
            UÑ     :  U*2 times

```
> 0 votes

# Answer
# Runic Enchantments, 12 bytes

```
"i1=?;3X4+k@

```

Try it online!

If it weren't for the "or any other value" having to print nothing I could save 2 bytes by removing `1=`, but that allows for values like `11` to also print the quine. Note that the ascii character `0x01` implicitly converts to `1` and is effectively also a `true` value. The only way to distinguish it from numerical `1` would be to concatenate it as a string.

### Explanation

The quine portion of this answer is actually pretty boring and straight forward, only `i1=?;` is added to meet challenge specifications:

```
"               Begin string mode
 i1=?;3X4+k@    Push the string literal i1=?;3X4+k@
"               Stop string mode
 i1=            Read input, compare to 1
    ?           Skip a number of instructions equal to the top of the stack (0 or 1)
     ;          If 0, terminate
      3X4+      If 1, push 34
          k     Convert to character (")
           @    Dump stack, top to bottom, to output and terminate.

```
> 0 votes

# Answer
# lin, 53 bytes

```
in (1g@ dup outln out ) e|
in (1g@ dup outln out ) e|

```

Takes input via STDIN. Truthy value is empty input, falsy value is any other input.

# Explanation

`in (...) e|` only executes whatever is within the parentheses if the input is empty. `1g@` retrieves the second line. `dup outln out` outputs 2 copies of the second line separated by a newline.

This takes advantage of the fact that lin only executes the program's first line (unless told otherwise by commands).
> 0 votes

# Answer
# Charcoal, 40 bytes

```
≔´η´¿´Ｎ´«´´´≔´Ｆ´η´⁺´´´´´ι´ηη¿Ｎ«´≔Ｆη⁺´´ιη

```

Try it online! I can't actually seem specify an input of an arbitrary type (I get some weird zero-length truthy value if I try), so this just inputs numeric values and prints itself for any non-zero value. This is based on the standard Charcoal quine in the linked answer, with the actual printing wrapped inside a conditional (+3 bytes) plus that code then quoted inside the assignment (+6 bytes). Charcoal no longer outputs a trailing newline which saves 1 byte. If an exact match with `1` is required, then for 46 bytes:

```
≔´η´¿´¬´⊖´Ｎ´«´´´≔´Ｆ´η´⁺´´´´´ι´ηη¿¬⊖Ｎ«´≔Ｆη⁺´´ιη

```

Try it online!
> 0 votes

# Answer
# Ruby `-n`, 46 bytes

Based on the Ruby heredoc quine. Falsy values are `nil` and `false`. Truthy values are basically every other valid Ruby object, including `true`, any number (even zero), any string (even the empty string), and any array (even an empty array).

```
puts <<2*2,2if eval$_
puts <<2*2,2if eval$_
2

```

Try it online!
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), 108 bytes

```
var s="var s={0}{1}{0};if(bool.Parse(ReadLine())Write(s,'{0}',s);";if(bool.Parse(ReadLine()))Write(s,'"',s);

```

Try it online!

The above link demonstrates the truthy case. Below are some alternative inputs:

Based on my C# quine.

Here is a lambda variation:

# C# (Visual C# Interactive Compiler), 79 bytes

```
b=>{var s="b=>{{var s={0}{1}{0};if(b)Write(s,'{0}',s);}}";if(b)Write(s,'"',s);}

```

Try it online!
> 0 votes

---
Tags: code-golf, quine
---


title: A curious prime fraction formula

text:
# Question
Title: A curious prime fraction formula
Given a positive integer \\$n\\$ output the integers \\$a\\$ and \\$b\\$ (forming **reduced** fraction \\$a/b\\$) such that:

$$\frac a b = \prod ^n \_{k=1} \frac {p^2\_k - 1} {p^2\_k + 1}$$

Where \\$p\_k\\$ is the \\$k\\$ th prime number (with \\$p\_1 = 2\\$).

Examples:

```
1   -> 3, 5
2   -> 12, 25
3   -> 144, 325
4   -> 3456, 8125
5   -> 41472, 99125
15  -> 4506715396450638759507001344, 11179755611058498955501765625
420 -> very long
```

Probabilistic prime checks are allowed, and it's ok if your answer fails due to limitations in your language's integer type.

---

Shortest code in bytes wins.

# Answer
# , 9 bytes

```
RÆN²‘İḤCP

```

Try it online!

### Trivia

Meet M!

M is a fork of Jelly, aimed at mathematical challenges. The core difference between Jelly and M is that M uses infinite precision for all internal calculations, representing results symbolically. Once M is more mature, Jelly will gradually become more multi-purpose and less math-oriented.

M is very much work in progress (full of bugs, and not really *that* different from Jelly right now), but it works like a charm for this challenge and I just couldn't resist.

### How it works

```
RÆN²‘İḤCP  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆN        Compute the kth primes for each k in that range.
   ²‘      Square and increment each prime p.
     İ     Invert; turn p² + 1 into the fraction 1 / (p² + 1).
      Ḥ    Double; yield 2 / (p² + 1).
       C   Complement; yield 1 - 2 / (p² + 1).
        P  Product; multiply all generated differences.

```
> 7 votes

# Answer
## Mathematica, 32 bytes

```
1##&@@(1-2/(Prime@Range@#^2+1))&

```

An unnamed function that takes integer input and returns the actual fraction.

This uses the fact that `(p<sup>2</sup>-1)/(p<sup>2</sup>+1) = 1-2/(p<sup>2</sup>+1)`. The code is then golfed thanks to the fact that Mathematica threads all basic arithmetic over lists. So we first create a list `{1, 2, ..., n}`, then retrieve all those primes and plug that list into the above expression. This gives us a list of all the factors. Finally, we multiply everything together by applying `Times` to the list, which can be golfed to `1##&`.

Alternatively, we can use `Array` for the same byte count:

```
1##&@@(1-2/(Prime~Array~#^2+1))&

```
> 10 votes

# Answer
## Python 2, 106 bytes

```
from fractions import*
n=input()
F=k=P=1
while n:b=P%k>0;n-=b;F*=1-Fraction(2*b,k*k+1);P*=k*k;k+=1
print F

```

The first and fourth lines hurt so much... it just turned out that using `Fraction` was better than multiplying separately and using `gcd`, even in Python 3.5+ where `gcd` resides in `math`.

Prime generation adapted from @xnor's answer here, which uses Wilson's theorem.
> 6 votes

# Answer
# Ruby, ~~122~~ ~~77~~ 65 bytes

Thanks to Sherlock for shaving off 10 bytes.

```
require'prime'
->n{Prime.take(n).map{|x|1-2r/(x*x+1)}.reduce(:*)}

```

Defines an anonymous function that takes a number and returns a `Rational`.
> 5 votes

# Answer
# Pyth, ~~26~~ 25

```
/RiFN=N*MCm,tdhd^R2.fP_ZQ

```

Try it here or run the Test Suite.

1 byte saved thanks to Jakube!

Pretty naive implementation of the specifications. Uses the spiffy "new" (I have no idea when this was added, but I've never seen it before) `P<neg>` which returns whether the positive value of a negative number is prime or not. Some of the mapping, etc can probably be golfed...
> 4 votes

# Answer
# PARI/GP, 33 bytes

```
n->prod(i=1,n,1-2/(prime(i)^2+1))

```

Alternate version (46 bytes):

```
n->t=1;forprime(p=2,prime(n),t*=1-2/(p^2+1));t

```

Non-competing version giving the floating-point (`t_REAL`) result (38 bytes):

```
n->prodeuler(p=2,prime(n),1-2/(p^2+1))

```
> 4 votes

# Answer
## Jelly, ~~14~~ 13 bytes

```
RÆN²µ’ż‘Pµ÷g/

```

Try it online! Thanks to @Dennis for -1 byte.

```
R                       Range [1..n]
 ÆN                     Nth prime
   ²                    Square
    µ                   Start new monadic chain
     ’ż‘                Turn each p^2 into [p^2-1, p^2+1]
        P               Product
         µ              Start new monadic chain
          ÷             Divide by...
           g/           Reduce GCD

```
> 4 votes

# Answer
# Julia, ~~59~~ 42 bytes

```
n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)

```

This is an anonymous function that accepts an integer and returns a `Rational` with `BigInt` numerator and denominator.

We begin by generating the list of prime numbers less than 2*n*2 and selecting the first *n* elements. This works because the *n*th prime is always less than *n*2 for all *n* \> 1. (See here.)

For each *p* of the *n* primes selected, we square *p* using elementwise power (`.^2`), and construct the rational 2 / (*p* \+ 1), where 2 is first converted to a `BigInt` to ensure sufficient precision. We subtract this from 1, take the product of the resulting array of rationals, and return the resulting rational.

Example usage:

```
julia> f = n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)
(anonymous function)

julia> f(15)
4506715396450638759507001344//11179755611058498955501765625

```

Saved 17 thanks to Sp3000!
> 4 votes

# Answer
## Convex, 28 bytes

Convex is a new language that I am developing that is heavily based on CJam and Golfscript. The interpreter and IDE can be found here. Input is an integer into the command line arguments. Indexes are one-based. Uses the CP-1252 encoding.

```
,:)_{µ²1-}%×\{µ²1+}%×¶_:Ðf/p

```

You may or may not consider this answer to be competing since I was working on a few features that this program uses before the challenge was posted, but the commit was made once I saw this challenge go out.
> 2 votes

# Answer
# MATL, 18 bytes

```
:Yq2^tqpwQpZd1Mhw/

```

**Try it online!**

Fails for large inputs because only integers up to `2^52` can be accurately represented internally.

### Explanation

```
:     % implicitly take input n. Generate range [1,...,n]
Yq    % first n prime numbers
2^    % square
tqp   % duplicate. Subtract 1. Product
wQp   % swap. Add 1. Product
Zd    % gcd of both products
1M    % push the two products again
h     % concatenate horizontally
w/    % swap. Divide by previously computed gcd. Implicitly display

```
> 2 votes

# Answer
# Mathematica, 45 bytes

```
Times@@Array[(Prime@#^2-1)/(Prime@#^2+1)&,#]&

```

Primes? Fractions? Mathematica.
> 2 votes

# Answer
# Haskell, 53 bytes

Anonymous function, **53** characters:

```
(scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!)

```

Try it here (note: in standard GHCi you need first to make sure `Data.Ratio` and `Data.List` are imported):

```
λ (scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!) 5
41472 % 99125
:: Integral a => Ratio a

```

Haskell's list indexing `!!` is 0-based. `(___!!)` is an *operator section*, forming an anonymous function so that `(xs !!) n == xs !! n`.

It's four bytes less to generate the whole sequence:

```
λ mapM_ print $ take 10 $     -- just for a nicer output
    scanl(*)1[1-2%(n*n+1)|n<-[2..],all((>0).rem n)[2..n-1]]
1 % 1
3 % 5
12 % 25
144 % 325
3456 % 8125
41472 % 99125
3483648 % 8425625
501645312 % 1221715625
18059231232 % 44226105625
4767637045248 % 11719917990625
:: IO ()

```
> 1 votes

# Answer
# Japt v2.0a0, 25 bytes

```
_j}jU £[X²ÉX²Ä]ÃyÈ×ÃË÷Fry

```

Try it
> 1 votes

# Answer
# Vyxal, 11 bytes

```
ʁǎ²₍‹›vΠ:ġḭ  # main program

```

```
ʁ            # range 0 to input
 ǎ²          # ith prime, sqaured
   ₍‹›       # push the increment and decrement of that list wrapped
      vΠ     # take the product of both lists
        :ġ   # duplicate, get the gcd
          ḭ  # divide both numbers by the gcd, print implicitly

```

I don't think the strategy of 1-2/p^2-1 works in Vyxal because it would just end with a floating point number rather than a fraction, but feel free to prove me wrong. (If it did work, it would be a literal translation from Dennis' M answer, but with a byte shaved off for the nth primes, coming out to 8)

Try it Online!
> 1 votes

# Answer
## Seriously, 25 bytes

```
,r`PªD;⌐k`M┬`π`Mi│g;)@\)\

```

Outputs `a\nb` (`\n` is a newline). Large inputs will take a long time (and might fail due to running out of memory) because prime generation is pretty slow.

Try it online!

Explanation:

```
,r`PªD;⌐k`M┬`π`Mi│g;)@\)\
,r                         push range(input)
  `PªD;⌐k`M                map:
   P                         k'th prime
    ª                        square
     D                       decrement
      ;                      dupe
       ⌐                     add 2 (results in P_k + 1)
        k                    push to list
           ┬               transpose
            `π`M           map product
                i│         flatten, duplicate stack
                  g;)      push two copies of gcd, move one to bottom of stack
                     @\    reduce denominator
                       )\  reduce numerator

```
> 0 votes

# Answer
# Husk, 11 bytes

```
Πmo§/→←□↑İp

```

Try it online!
> 0 votes

# Answer
# , 18 bytes

```
[:*/1-2%1+*:@p:@i.

```

Try it online!

Uses the same formula that Martin Ender's answer does.
> 0 votes

---
Tags: code-golf, arithmetic, primes
---


title: Ploughed fields via moduli

text:
# Question
Title: Ploughed fields via moduli
Let \\$R, C\\$ be positive integers and let \\$0 \< s \leq 1\\$. Consider the \\$R \times C\\$ **matrix** \\$\mathbf M\\$ defined as \begin{equation} M(i,j) = \frac{\mathrm{mod}\\,(j, i^s)}{R^s}, \quad i = 1, \ldots, R, \quad j = 1, \ldots, C \end{equation} where \\$\\,\mathrm{mod}\\,\\$ denotes the modulo operation: for \\$a,b \> 0\\$ not necessarily integer, \\$\mathrm{mod}\\,(a,b) = c\\$ if and only if \\$0 \leq c \< b\\$ and \\$a = b\cdot k + c\\$ with \\$k\\$ integer.

Note that \\$0 \leq M(i,j) \< 1\\$.

The matrix \\$\mathbf M \\$ can be displayed as an image, where the value of each entry determines the color of a pixel, using a **colormap** to translate numbers between \\$0\\$ and \\$1\\$ into colors. The simplest colormap is to directly consider each number as grey intensity, with \\$0\\$ corresponding to black and \\$1\\$ to white.

As an example, \\$R=500\\$, \\$C=800\\$, \\$s=0.8\\$ with the grey colormap give the following image:

# The challenge

Given two positive integers \\$100 \leq R, C \leq 2000 \\$ and a number \\$0 \< s \leq 1\\$, display the above defined matrix \\$\mathbf M\\$ as an image. You can use any colormap of your choice, not necessarily consistent across images, as long as it satisfies the very lax requirements described next.

# Colormap requirements

1. At least \\$16\\$ different colours.
2. Reasonably gradual changes between adjacent colours.
3. The first and last colours should be clearly different.

Although the terms *reasonably gradual* and *clearly different* are somewhat subjective, this is not likely to be a contentious point. The sole purpose of these requirements is to prevent abuse. If your programming language offers a default colormap, it is most likely fine. If it doesn't, using grey is probably the shortest option.

# Additional rules

* **Graphical output** is required, with output being flexible as usual.
* The image should have the correct **orientation**, with \\$M(1,1)\\$ corresponding to the upper-left corner.
* The image should have the **aspect ratio** given by \\$R\\$ and \\$C\\$. That is, each entry of \\$\mathbf M\\$ should correspond to a square pixel.
* If the image is output by displaying it on the screen, it is not necessary that each screen pixel corresponds to an image pixel. That is, the **display scaling is flexible** (but the aspect ratio should be kept).
* **Auxiliary elements** such as axis labels, grid lines or a white frame are not required, but are allowed.
* Programs or functions are accepted. Standard loopholes are forbidden.
* Shortest code in bytes wins.

# Test cases

Each of the following uses a different colormap, to illustrate some possibilities (and not incidentally to produce lively pictures).

| Inputs: `R`, `C`, `s` | Output |
| --- | --- |
| `500`, `800`, `0.8` |  |
| `600`, `1000`, `0.7` |  |
| `800`, `800`, `0.9` |  |
| `500`, `900`, `1` |  |
| `700`, `1200`, `0.6` |  |
| `200`, `250`, `0.3` |  |

# Answer
# Wolfram Language (Mathematica), 39 bytes

```
sImage@Array[Mod[#2,#^s]&,{##}]/#^s&

```

Try it online!

Input `[s][R, C]`.
> 4 votes

# Answer
# Haskell, 131 bytes

```
f=fromIntegral
u=unwords.map show
a%b|a>b=(a-b)%b|1<2=a
(r#c)s="P2":u[c,r,99]:[u[round$f j%(f i**s)/f r**s*99|j<-[1..c]]|i<-[1..r]]

```

Try it online!

`(r#c)s` returns the lines of a PGM file.

After writing it like this, I learned I could probably just return a matrix of float values but I don't think that's very interesting.
> 6 votes

# Answer
# , 51 bytes

```
load'viewmat'
1 :'[:viewmat(|~^&u)"0~/&(1+i.)%u^~['

```

Try it online!

A J adverb, which uses the library function `viewmat` to do all the heavy lifting -- we merely need to construct the matrix values.

Assuming the adverb has been assigned to `f`, called like:

```
500 (0.8 f) 800

```

## 500 800 0.8

## 200 250 0.3
> 6 votes

# Answer
# Python 3, ~~116~~ ~~114~~118 bytes

-2 thanks to some basic pointers from hyper-neutrino
+4 to correct an off-by-one error, thanks Tipping Octopus

```
from matplotlib.pylab import*
def M(R,C,s):
 imshow([[j%i**s/R**s for j in range(1,C+1)]for i in range(1,R+1)]);show()

```

Fairly straightforward, my first code golf attempt so I may be missing something easily golfable. Executes nested list comprehension inside the imshow() to immediately create image. Needs the show() to actually display the image.

## 700, 1200, 0.6
> 4 votes

# Answer
# JavaScript + HTML, 156 bytes

```
(R,C,s)=>{for((w=x=>document.write(x))`<table cellspacing=0>`,i=0;i++<R;)for(w`<tr>`,j=0;j<C;)w(`<td bgcolor=#${((++j%i**s*16/R**s|0)*273).toString(16)}>`)}

```
* -7 bytes by Shaggy

```
; (function run() {

f=

(R,C,s)=>{for((w=x=>document.write(x))`<table cellspacing=0>`,i=0;i++<R;)for(w`<tr>`,j=0;j<C;)w(`<td bgcolor=#${((++j%i**s*16/R**s|0)*273).toString(16)}>`)}

R = /*R{*/500/*}*/;
C = /*C{*/800/*}*/;
s = /*s{*/0.8/*}*/;

document.write(`
<div style="margin-bottom: 10px;">
  <label> R = <input id="inputR" type="number" step="1" value="${R}" oninput="UpdateJS()" /></label><br />
  <label> C = <input id="inputC" type="number" step="1" value="${C}" oninput="UpdateJS()" /></label><br />
  <label> s = <input id="inputS" type="number" step="0.01" value="${s}" oninput="UpdateJS()" /></label><br />
  <form action="${location.href}" method="post">
    <input id="inputJs" type="hidden" name="js" />
    <input type="hidden" name="css" />
    <input type="hidden" name="html" />
    <input type="hidden" name="console" value="false" />
    <input type="hidden" name="babel" value="false" />
    <button type="submit">Draw</button>
  </form>
</div>
`)

f(R, C, s);

UpdateJS = function () {
  R = inputR.value;
  C = inputC.value;
  s = inputS.value;
  js = `; (${run}());`
    .replace(/\/\*R\{\*\/.*?\/\*\}\*\//, `/*R{*/${R}/*}*/`)
    .replace(/\/\*C\{\*\/.*?\/\*\}\*\//, `/*C{*/${C}/*}*/`)
    .replace(/\/\*s\{\*\/.*?\/\*\}\*\//, `/*s{*/${s}/*}*/`);
  inputJs.value = js;
};

UpdateJS();

}());
```
> 4 votes

# Answer
# K (oK) + `iKe`, 61 bytes

```
{w::y;h::x;p::pow[;z];,(;gray;+_255*((p 1+!h)!\:/:1+!w)%p w)}

```

Try it online!

Shortened heavily and made to work with the help of JohnE and coltim at the k tree.

A function which takes input as `R, C, s`.
> 4 votes

# Answer
# , 66 bytes

```
function(R,C,s)cat('P2',C,R,99,(99*outer(1:C,(1:R)^s,`%%`))%/%R^s)

```

Try it online!

I kinda think that pajonk's answer is close to the shortest possible using 's built-in graphics... so here's a completely different approach, which actually turns-out to be 4 bytes shorter...

Outputs the contents of a greyscale PGM file. At least on my laptop using Apple's 'Preview' program, the newline characters separating lines appear to be superfluous.

Here's Preview's display of the the output of `ploughed_field(500,800,.8)`:
> 4 votes

# Answer
# Python 3, 90 73 bytes

```
from pylab import*;ion()
def M(R,C,s):imshow(-~r_[:C]%c_[1:R+1]**s/R**s)

```

Heavily based on Danica's answer, I would have commented but I have 0 reputation.

Shorter import statement

`ion()` to show instead of `;show()`

`arange` (from `numpy.arange`) array approach for faster performance and fewer bytes

remove def function indent

```
   from pylab import*
   ion()
   def M(R,C,s):imshow((arange(C)+1)%(arange(R)+1)[:,None]**s/R**s)

```

Thanks to ovs this shortens to 74 bytes

And a `-~` trick removes 1 byte from `r_[1:C+1]`
> 4 votes

# Answer
# , ~~84~~ 70 bytes

*-14 bytes thanks to @Dominic*

```
function(R,C,s)image(outer(1:C,(R:1)^s,`%%`)/R^s,c=rainbow(64),as=R/C)

```

Try it online!

Try it on rdrr.io with graphical output
> 3 votes

# Answer
# Red, 137 bytes

```
func[r c s][i: make image! to[]as-pair c r k: 0
repeat y r[repeat x c[i/(k: k + 1): to 1.1.1 to[](to 1 x %(y ** s)/(r ** s)* 255)]]?(i)]

```

`f 500 800 0.8`
> 2 votes

---
Tags: code-golf, number, arithmetic, graphical-output
---


title: Number of distinct shadow transforms

text:
# Question
Title: Number of distinct shadow transforms
## Background

**Shadow transform** of a 0-based integer sequence \\$a(n)\\$ is another 0-based integer sequence \\$s(n)\\$ defined with the following equation:

$$ s(n) = \sum\_{i=0}^{n-1}{(1 \text{ if } n \text{ divides } a(i), 0 \text{ otherwise})} $$

i.e. \\$s(n)\\$ is the number of terms in \\$a(0), \cdots, a(n-1)\\$ that are divisible by \\$n\\$.

\\$s(0)\\$ is always 0 because there are zero terms to consider, and \\$s(1)\\$ is always 1 because \\$a(0)\\$ is always divisible by 1. \\$s(2)\\$ may have a value of 0, 1, or 2, depending on how many terms out of \\$a(0)\\$ and \\$a(1)\\$ are even.

## Challenge

Given a non-negative integer \\$n\\$, compute the number of distinct shadow transforms of length \\$n\\$. This sequence is A226443.

The following is the list of first 11 terms for \\$n = 0, \cdots, 10\\$, as listed on the OEIS page.

```
1, 1, 1, 3, 12, 48, 288, 1356, 10848, 70896, 588480

```

**Explanation:** Let's call this sequence \\$f(n)\\$.

* \\$f(0)\\$ counts the number of empty sequences, which is 1 (since `[]` counts).
* \\$f(1)\\$ counts the possible number of `[s(0)]` which can only be `[0]`.
* \\$f(2)\\$ counts `[s(0),s(1)]`s which can only be `[0,1]`.
* Since `s(2)` can take any of 0, 1, or 2 independent of `s(0)` and `s(1)`, \\$f(3)\\$ is 3.
* `s(3)` is also independent of `s(0)` through `s(2)` (because 3 is relatively prime to 2) and take a value between 0 and 3 inclusive, so \\$f(4) = 3 \cdot 4 = 12\\$.
* Finding \\$f(5)\\$ is slightly more complex because `s(4)` is tied with `s(2)`. If `s(4) == 4`, all of `a(0)..a(3)` must be divisible by 4 (and therefore even), and `s(2)` can only be 2. If `s(4) == 3`, at least one of `a(0)` or `a(1)` must be even, and `s(2)` must be 1 or 2. Therefore, \\$f(5) = 12 + 12 + 12 + 8 + 4 = 48\\$.

Standard rules apply. I/O does NOT apply. The shortest code in bytes wins.

# Answer
> 4 votes
# Jelly, 13 bytes

Thanks to @ovs for the fix.

```
%Lċ0
*ṗ’ÇƤ€QL

```

Try it online!

The first line computes the shadow transform.

The second line looks at the shadow transform of all sequences of length `n` with elements in `{1, 2, ..., n^n}`.

# Answer
> 3 votes
# Python 2 (PyPy), ~~228~~ 225 bytes

This is based on the first PARI implementation on OEIS and computes terms up to \\$n=6\\$ on TIO.

```
import math,itertools as I
L=math.log
R=range
n=input()
P=k=r=1
while k<n:k+=1;r*=k**int(P%k*L(n+.5)/L(k));P*=k*k
print len({tuple(sum(x%o<1for x in s[:o])for o in R(n))for s in I.product(*[[i+1for i in R(r)if-1<r%~i]]*~-n)})

```

Try it online!

---

Naive bruteforcing is obviously a lot shorter (100 bytes):

```
lambda n,R=range:len({tuple(sum(s/n**(n*x)%n**n%o<1for x in R(o))for o in R(n))for s in R(n**n**2)})

```

Try it online! Crashes for \\$n=4\\$ with a *MemoryError*, when `R(n**n**2)` tries to create a list of \\$2^{32}\\$ integers.

---
Tags: code-golf, math, sequence, number-theory
---