title: Print all 3 by 3 sturdy squares

text:
# Question
Title: Print all 3 by 3 sturdy squares
A sturdy square (akin to a magic square) is an arrangement of the integers 1 to \\$N^2\\$ on an \\$N\\$ by \\$N\\$ grid such that every 2 by 2 subgrid has the same sum.

For example, for \\$N = 3\\$ one sturdy square is

```
1 5 3
9 8 7
4 2 6

```

because the four 2 by 2 subgrids

```
1 5
9 8
```

```
5 3
8 7
```

```
9 8
4 2
```

```
8 7
2 6
```

all sum to the same amount, 23:

$$23 = 1 + 5 + 9 + 8 = 5 + 3 + 8 + 7 = 9 + 8 + 4 + 2 = 8 + 7 + 2 + 6$$

Now there are sturdy squares for higher values of N and even rectangular versions but your only task in this challenge is to output all possible 3 by 3 sturdy squares. There are exactly 376 distinct 3 by 3 sturdy squares, including those that are reflections or rotations of others, and not all of them have the same sum of 23.

Write a program or function that takes no input but prints or returns a string of all 376 sturdy squares in any order, separated by empty lines, with up to two optional trailing newlines. Each square should consist of three lines of three space separated nonzero decimal digits.

Here is a valid output example:

```
1 5 3
9 8 7
4 2 6

1 5 6
8 7 3
4 2 9

1 5 6
8 9 3
2 4 7

1 5 7
9 6 3
2 4 8

1 6 2
8 9 7
4 3 5

1 6 2
9 7 8
4 3 5

1 6 3
9 8 7
2 5 4

1 6 7
8 5 2
3 4 9

1 6 7
9 4 3
2 5 8

1 7 2
9 4 8
5 3 6

1 7 2
9 6 8
3 5 4

1 7 4
8 3 5
6 2 9

1 7 4
9 2 6
5 3 8

1 7 6
9 2 4
3 5 8

1 8 2
5 9 4
6 3 7

1 8 3
6 5 4
7 2 9

1 8 3
9 2 7
4 5 6

1 8 4
5 7 2
6 3 9

1 8 4
6 9 3
2 7 5

1 8 4
9 3 6
2 7 5

1 8 6
7 3 2
4 5 9

1 9 2
5 6 4
7 3 8

1 9 2
6 4 5
7 3 8

1 9 2
6 8 5
3 7 4

1 9 2
8 3 7
4 6 5

1 9 3
7 2 5
6 4 8

1 9 3
7 6 5
2 8 4

1 9 4
5 8 2
3 7 6

1 9 4
6 7 3
2 8 5

1 9 4
8 2 5
3 7 6

1 9 5
7 2 3
4 6 8

1 9 5
7 4 3
2 8 6

2 3 5
9 8 6
4 1 7

2 3 6
9 7 5
4 1 8

2 4 3
8 9 7
5 1 6

2 4 3
9 7 8
5 1 6

2 4 6
7 8 3
5 1 9

2 4 7
8 9 3
1 5 6

2 4 8
9 6 3
1 5 7

2 5 3
9 4 8
6 1 7

2 5 4
9 3 7
6 1 8

2 5 4
9 8 7
1 6 3

2 5 7
6 8 1
4 3 9

2 5 7
6 9 1
3 4 8

2 5 8
7 6 1
3 4 9

2 5 8
9 4 3
1 6 7

2 6 1
7 9 8
5 3 4

2 6 1
8 7 9
5 3 4

2 6 3
5 9 4
7 1 8

2 6 4
5 8 3
7 1 9

2 6 7
9 1 4
3 5 8

2 6 8
7 4 1
3 5 9

2 7 1
8 4 9
6 3 5

2 7 1
8 6 9
4 5 3

2 7 3
5 6 4
8 1 9

2 7 3
6 4 5
8 1 9

2 7 3
9 1 8
5 4 6

2 7 5
4 8 1
6 3 9

2 7 5
6 9 3
1 8 4

2 7 5
9 3 6
1 8 4

2 8 1
4 9 5
7 3 6

2 8 4
7 6 5
1 9 3

2 8 5
4 9 1
3 7 6

2 8 5
6 7 3
1 9 4

2 8 6
7 4 3
1 9 5

2 9 1
4 6 5
8 3 7

2 9 1
5 4 6
8 3 7

2 9 1
5 8 6
4 7 3

2 9 1
7 3 8
5 6 4

2 9 3
6 1 5
7 4 8

2 9 4
3 7 1
6 5 8

2 9 4
3 8 1
5 6 7

2 9 5
4 7 1
3 8 6

2 9 5
7 1 4
3 8 6

2 9 6
5 3 1
4 7 8

2 9 6
5 4 1
3 8 7

3 2 5
9 8 7
4 1 6

3 2 6
8 9 5
4 1 7

3 2 7
9 6 5
4 1 8

3 4 2
7 9 8
6 1 5

3 4 2
8 7 9
6 1 5

3 4 5
9 2 7
6 1 8

3 4 8
6 9 1
2 5 7

3 4 9
7 6 1
2 5 8

3 4 9
8 5 2
1 6 7

3 5 1
7 8 9
6 2 4

3 5 2
8 4 9
7 1 6

3 5 4
9 1 8
6 2 7

3 5 4
9 6 8
1 7 2

3 5 8
9 1 4
2 6 7

3 5 8
9 2 4
1 7 6

3 5 9
7 4 1
2 6 8

3 6 1
7 8 9
4 5 2

3 6 2
4 9 5
8 1 7

3 6 8
7 1 2
4 5 9

3 7 2
4 6 5
9 1 8

3 7 2
5 4 6
9 1 8

3 7 2
8 1 9
6 4 5

3 7 4
6 1 5
8 2 9

3 7 4
6 8 5
1 9 2

3 7 6
4 9 1
2 8 5

3 7 6
5 8 2
1 9 4

3 7 6
8 2 5
1 9 4

3 8 1
4 5 6
9 2 7

3 8 1
7 2 9
6 5 4

3 8 4
2 9 1
6 5 7

3 8 6
4 7 1
2 9 5

3 8 6
7 1 4
2 9 5

3 8 7
5 4 1
2 9 6

3 9 1
5 2 7
8 4 6

3 9 1
5 6 7
4 8 2

3 9 2
5 1 6
8 4 7

3 9 4
2 6 1
7 5 8

3 9 4
2 8 1
5 7 6

3 9 6
4 2 1
5 7 8

3 9 6
5 1 2
4 8 7

4 1 6
9 8 7
3 2 5

4 1 7
8 9 5
3 2 6

4 1 7
9 8 6
2 3 5

4 1 8
9 6 5
3 2 7

4 1 8
9 7 5
2 3 6

4 2 6
9 8 7
1 5 3

4 2 7
6 9 3
5 1 8

4 2 7
9 3 6
5 1 8

4 2 8
7 6 3
5 1 9

4 2 9
8 7 3
1 5 6

4 3 5
8 9 7
1 6 2

4 3 5
9 2 8
6 1 7

4 3 5
9 7 8
1 6 2

4 3 7
5 8 2
6 1 9

4 3 7
8 2 5
6 1 9

4 3 7
9 1 6
5 2 8

4 3 9
6 8 1
2 5 7

4 5 2
7 3 9
8 1 6

4 5 2
7 8 9
3 6 1

4 5 3
8 1 9
7 2 6

4 5 3
8 6 9
2 7 1

4 5 6
3 8 1
7 2 9

4 5 6
9 2 7
1 8 3

4 5 9
7 1 2
3 6 8

4 5 9
7 3 2
1 8 6

4 6 2
3 8 5
9 1 7

4 6 5
2 9 1
7 3 8

4 6 5
8 3 7
1 9 2

4 6 8
7 2 3
1 9 5

4 7 1
5 3 8
9 2 6

4 7 1
6 2 9
8 3 5

4 7 3
5 1 6
9 2 8

4 7 3
5 8 6
2 9 1

4 7 5
2 6 1
8 3 9

4 7 8
5 3 1
2 9 6

4 8 1
2 7 5
9 3 6

4 8 1
3 9 6
5 7 2

4 8 1
6 3 9
5 7 2

4 8 2
5 6 7
3 9 1

4 8 3
1 9 2
7 5 6

4 8 6
3 2 1
7 5 9

4 8 7
5 1 2
3 9 6

4 9 1
2 8 5
6 7 3

4 9 1
3 7 6
5 8 2

4 9 1
5 2 8
6 7 3

4 9 2
1 7 3
8 5 6

4 9 2
1 8 3
7 6 5

4 9 3
1 6 2
8 5 7

4 9 3
1 8 2
6 7 5

4 9 5
2 3 1
7 6 8

4 9 5
3 1 2
7 6 8

4 9 6
3 2 1
5 8 7

5 1 6
8 9 7
2 4 3

5 1 6
9 7 8
2 4 3

5 1 8
6 9 3
4 2 7

5 1 8
9 3 6
4 2 7

5 1 9
7 6 3
4 2 8

5 1 9
7 8 3
2 4 6

5 2 3
7 8 9
6 1 4

5 2 8
7 3 4
6 1 9

5 2 8
9 1 6
4 3 7

5 3 2
6 8 9
7 1 4

5 3 4
7 9 8
2 6 1

5 3 4
8 2 9
7 1 6

5 3 4
8 7 9
2 6 1

5 3 6
9 4 8
1 7 2

5 3 8
4 7 1
6 2 9

5 3 8
7 1 4
6 2 9

5 3 8
9 2 6
1 7 4

5 4 3
7 2 9
8 1 6

5 4 6
3 7 2
8 1 9

5 4 6
9 1 8
2 7 3

5 6 4
1 9 2
8 3 7

5 6 4
7 3 8
2 9 1

5 6 7
3 8 1
2 9 4

5 7 2
1 8 4
9 3 6

5 7 2
3 9 6
4 8 1

5 7 2
6 3 9
4 8 1

5 7 4
1 6 2
9 3 8

5 7 6
2 3 1
8 4 9

5 7 6
2 8 1
3 9 4

5 7 6
3 1 2
8 4 9

5 7 8
4 2 1
3 9 6

5 8 2
1 9 4
6 7 3

5 8 2
3 7 6
4 9 1

5 8 7
3 2 1
4 9 6

5 9 1
3 2 7
8 6 4

5 9 1
3 4 7
6 8 2

5 9 2
1 7 4
6 8 3

5 9 2
4 1 7
6 8 3

5 9 4
1 3 2
8 6 7

5 9 4
2 1 3
8 6 7

6 1 4
7 8 9
5 2 3

6 1 5
7 9 8
3 4 2

6 1 5
8 7 9
3 4 2

6 1 7
9 2 8
4 3 5

6 1 7
9 4 8
2 5 3

6 1 8
9 2 7
3 4 5

6 1 8
9 3 7
2 5 4

6 1 9
5 8 2
4 3 7

6 1 9
7 3 4
5 2 8

6 1 9
8 2 5
4 3 7

6 2 3
5 9 8
7 1 4

6 2 4
7 8 9
3 5 1

6 2 7
9 1 8
3 5 4

6 2 8
5 4 3
7 1 9

6 2 9
4 7 1
5 3 8

6 2 9
7 1 4
5 3 8

6 2 9
8 3 5
1 7 4

6 3 2
5 7 9
8 1 4

6 3 5
8 4 9
2 7 1

6 3 7
5 2 4
8 1 9

6 3 7
5 9 4
1 8 2

6 3 9
4 8 1
2 7 5

6 3 9
5 7 2
1 8 4

6 4 2
3 8 7
9 1 5

6 4 5
2 7 3
9 1 8

6 4 5
8 1 9
3 7 2

6 4 8
7 2 5
1 9 3

6 5 1
3 7 8
9 2 4

6 5 1
3 9 8
7 4 2

6 5 4
1 8 3
9 2 7

6 5 4
7 2 9
3 8 1

6 5 7
2 4 1
8 3 9

6 5 7
2 9 1
3 8 4

6 5 8
3 2 1
7 4 9

6 5 8
3 7 1
2 9 4

6 7 1
4 2 9
8 5 3

6 7 3
1 9 4
5 8 2

6 7 3
2 8 5
4 9 1

6 7 3
5 2 8
4 9 1

6 7 5
1 3 2
9 4 8

6 7 5
1 8 2
4 9 3

6 7 5
2 1 3
9 4 8

6 8 1
2 3 7
9 5 4

6 8 2
3 4 7
5 9 1

6 8 3
1 7 4
5 9 2

6 8 3
4 1 7
5 9 2

6 8 4
1 2 3
9 5 7

6 9 2
1 3 5
8 7 4

6 9 2
1 4 5
7 8 3

6 9 3
1 2 4
8 7 5

6 9 3
2 1 5
7 8 4

6 9 4
1 2 3
7 8 5

7 1 4
5 9 8
6 2 3

7 1 4
6 8 9
5 3 2

7 1 6
8 2 9
5 3 4

7 1 6
8 4 9
3 5 2

7 1 8
5 9 4
2 6 3

7 1 9
5 4 3
6 2 8

7 1 9
5 8 3
2 6 4

7 2 3
5 6 9
8 1 4

7 2 4
3 9 6
8 1 5

7 2 4
6 3 9
8 1 5

7 2 6
8 1 9
4 5 3

7 2 9
3 8 1
4 5 6

7 2 9
6 5 4
1 8 3

7 3 4
2 8 5
9 1 6

7 3 4
5 2 8
9 1 6

7 3 4
6 1 9
8 2 5

7 3 6
4 2 5
9 1 8

7 3 6
4 9 5
2 8 1

7 3 8
2 9 1
4 6 5

7 3 8
5 6 4
1 9 2

7 3 8
6 4 5
1 9 2

7 4 2
3 9 8
6 5 1

7 4 8
6 1 5
2 9 3

7 4 9
3 2 1
6 5 8

7 5 1
3 6 9
8 4 2

7 5 2
1 8 6
9 3 4

7 5 2
1 9 6
8 4 3

7 5 6
1 4 2
9 3 8

7 5 6
1 9 2
4 8 3

7 5 8
2 6 1
3 9 4

7 5 9
3 2 1
4 8 6

7 6 1
2 5 8
9 4 3

7 6 1
3 4 9
8 5 2

7 6 2
4 1 9
8 5 3

7 6 5
1 8 3
4 9 2

7 6 8
2 3 1
4 9 5

7 6 8
3 1 2
4 9 5

7 8 3
1 4 5
6 9 2

7 8 4
2 1 5
6 9 3

7 8 5
1 2 3
6 9 4

8 1 4
5 6 9
7 2 3

8 1 4
5 7 9
6 3 2

8 1 5
3 9 6
7 2 4

8 1 5
6 3 9
7 2 4

8 1 6
7 2 9
5 4 3

8 1 6
7 3 9
4 5 2

8 1 7
4 9 5
3 6 2

8 1 9
3 7 2
5 4 6

8 1 9
5 2 4
6 3 7

8 1 9
5 6 4
2 7 3

8 1 9
6 4 5
2 7 3

8 2 4
3 6 7
9 1 5

8 2 5
4 3 7
9 1 6

8 2 5
6 1 9
7 3 4

8 2 6
3 4 5
9 1 7

8 2 9
6 1 5
3 7 4

8 3 5
1 7 4
9 2 6

8 3 5
4 1 7
9 2 6

8 3 5
6 2 9
4 7 1

8 3 7
1 9 2
5 6 4

8 3 7
4 6 5
2 9 1

8 3 7
5 4 6
2 9 1

8 3 9
2 4 1
6 5 7

8 3 9
2 6 1
4 7 5

8 4 2
3 6 9
7 5 1

8 4 3
1 9 6
7 5 2

8 4 6
5 2 7
3 9 1

8 4 7
5 1 6
3 9 2

8 4 9
2 3 1
5 7 6

8 4 9
3 1 2
5 7 6

8 5 2
1 6 7
9 4 3

8 5 2
3 4 9
7 6 1

8 5 3
4 1 9
7 6 2

8 5 3
4 2 9
6 7 1

8 5 6
1 2 3
9 4 7

8 5 6
1 7 3
4 9 2

8 5 7
1 6 2
4 9 3

8 6 2
1 4 7
9 5 3

8 6 3
2 1 7
9 5 4

8 6 4
3 2 7
5 9 1

8 6 7
1 3 2
5 9 4

8 6 7
2 1 3
5 9 4

8 7 4
1 3 5
6 9 2

8 7 5
1 2 4
6 9 3

9 1 5
3 6 7
8 2 4

9 1 5
3 8 7
6 4 2

9 1 6
2 8 5
7 3 4

9 1 6
4 3 7
8 2 5

9 1 6
5 2 8
7 3 4

9 1 7
3 4 5
8 2 6

9 1 7
3 8 5
4 6 2

9 1 8
2 7 3
6 4 5

9 1 8
4 2 5
7 3 6

9 1 8
4 6 5
3 7 2

9 1 8
5 4 6
3 7 2

9 2 4
3 7 8
6 5 1

9 2 6
1 7 4
8 3 5

9 2 6
4 1 7
8 3 5

9 2 6
5 3 8
4 7 1

9 2 7
1 8 3
6 5 4

9 2 7
4 5 6
3 8 1

9 2 8
5 1 6
4 7 3

9 3 4
1 8 6
7 5 2

9 3 6
1 8 4
5 7 2

9 3 6
2 7 5
4 8 1

9 3 8
1 4 2
7 5 6

9 3 8
1 6 2
5 7 4

9 4 3
1 6 7
8 5 2

9 4 3
2 5 8
7 6 1

9 4 7
1 2 3
8 5 6

9 4 8
1 3 2
6 7 5

9 4 8
2 1 3
6 7 5

9 5 3
1 4 7
8 6 2

9 5 4
2 1 7
8 6 3

9 5 4
2 3 7
6 8 1

9 5 7
1 2 3
6 8 4
```

Your program must produce these same 376 sturdy squares, just not necessarily in this order. The output does not need to be deterministic, i.e. you could output them in different orders on different runs as long as they are all there.

**The shortest code in bytes wins.**

The topic of sturdy squares originated with this chat message of mine which led to a large amount of discussion on their properties and how to generate them. Props to Peter Taylor, feersum, and Sp3000 for continuing the discussion, and especially to El'endia Starman for drafting a corresponding OEIS sequence.

# Answer
# Pyth, ~~38~~ ~~34~~ ~~33~~ 32 bytes

```
Vfq2l{sMX2.DR2.:T5b.pS9Vc3NjdH)k

```

*5 bytes saved in formatting by Jakube*

*1 byte saved by switching to Peter Taylor's substrings of length five, remove the middles approach*

Takes about a minute and a half to run on my machine.

How it works at the high level:

* Generate all permutations (`.pS9`)
* Form length 5 substrings (`.:T5`)
* Remove the center element of each (`.DR2`)
* Append a newline to the center element, marking it with a necessarily different sum (`X2 ... b`)
* Filter for the squares where all such sums are equal (`fq2l{`)
* Format and print (`V ... Vc3NjdH)k`)
> 9 votes

# Answer
## Python 3, ~~169~~ ~~168~~ 164 bytes

Took the program I used to investigate these sturdy squares/rectangles and golfed it wayyyy down. Golfed off 4 bytes thanks to otakucode.

```
from itertools import*
r=range(1,10)
for p in permutations(r,6):
 x,y=p[0],p[5];q=p[:5]+(x+p[3]-p[2],y,y+p[1]-x,p[2]+y-x)
 if set(q)==set(r):print('%s %s %s\n'*3%q)

```

### Explanation

Given a partially-filled sturdy square like this,

```
a b c
d e ?
g ? ?

```

The remaining three entries are uniquely determined, and are `a+d-c`, `a+b-g`, and `c+g-a`. So I generate all permutations of 0..8 with six elements, calculate the rest, and then check to see whether the set of this is the same as the set of 0..8. If it is, I print out the grid.

---

For reference, here's the original (with comments and extraneous code removed):

```
from itertools import permutations as P

n = 3
m = 3
permutes = P(range(m*n), m+n)

counter = 0
for p in permutes:
    grid = [p[:n]]
    for i in range(m-1):
        grid.append([p[n+i]]+[-1]*(n-1))
    grid[1][1] = p[-1]

    s = p[0]+p[1]+p[n]+p[-1]

    has = list(p)

    fail = 0
    for y in range(1,m):
        for x in range(1,n):
            if x == y == 1: continue

            r = s-(grid[y-1][x-1] + grid[y-1][x] + grid[y][x-1])

            if r not in has and 0 <= r < m*n:
                grid[y][x] = r
                has.append(r)
            else:
                fail = 1
                break

        if fail: break

    if not fail:
        counter += 1

print(counter)

```
> 10 votes

# Answer
# CJam, ~~40~~ 38 bytes

```
A,1>e!3f/{2{2few:::+z}*:|,1=},Ma*Sf*N*

```

*Thanks to @PeterTaylor for golfing off 2 bytes!*

This finishes instantly using the Java interpreter. It works using the online interpreter as well, but it requires a little patience. Try it online.

### Test run

```
$ cjam sturdy-squares.cjam | head -n 8
1 5 3
9 8 7
4 2 6

1 5 6
8 7 3
4 2 9

$ cjam sturdy-squares.cjam | tail -n 8

9 5 4
2 3 7
6 8 1

9 5 7
1 2 3
6 8 4
$

```

### How it works

```
A,1>     e# Push [1 ... 9].
e!       e# Push the array of all permutations of that array.
3f/      e# Split each into rows of length 3.
{        e# Filter; push the permutation, then:
  2{     e#   Do the following twice:
    2few e#     Split each row into overlapping splices of length 2.
         e#       [a b c] -> [[a b] [b c]]
    :::+ e#     Reduce each innermost vector to its sum.
         e#       [[a b] [b c]] -> [a+b b+c]
    z    e#     Transpose rows with columns.
  }*     e#   The result is [[s t] [u v]], the sums of all 2x2 squares.
  :|     e#   Perform set union of the pairs of sums.
  ,1=    e#   Check if the length of the result is 1 (unique sum).
},       e# Keep the array if the result was 1.
{        e# For each kept array:
  Sf*    e#   Join the elements of its rows, separating by spaces.
  ~M     e#   Dump the resulting strings and an empty string on the stack.
}%       e# Collect everything in an array.
N*       e# Join the strings, separating by linefeeds.

```
> 8 votes

# Answer
# Python 3.5, 135 bytes

```
from itertools import*
for x in permutations(range(1,10)):eval((("=="+"+x[%s]"*3)*4)[2:]%(*"013125367578",))and print("%d %d %d\n"*3%x)

```

Directly checks the sum of each square, minus the middle. Most likely still golfable by the "`itertools` is unnecessary" rule-of-thumb.
> 6 votes

# Answer
# Mathematica ~~147 166 155~~ 149 bytes

This generates the permutations of {1,2,3...9} and selects cases for which

(sum of digits at positions {1,2,4,5}) =

(sum of digits at positions {2,3,5,6}) =

(sum of the digits at positions {4,5,7,8}) =

(sum of the digits at positions {5,6,8,9})

```
f@s_:=Length@Tally[Tr@Extract[s,#]&/@Table[{{0},{1},{3},{4}}+k,{k,{1,2,4,5}}]]>1;
Row[Grid/@(#~Partition~3&/@Select[Permutations@Range@9,f@#&]),"\n"]

```

**Output** (a partial look)

---

```
Length[%]

```

> 376
> 5 votes

# Answer
## CJam (39 37 bytes)

```
A,1>e!{5ew{2Mtz}2*::+)-!},3f/Ma*Sf*N*

```

Online demo (warning: may take over a minute to run, triggering "Abort this script?" prompts from the browser).

Works by filtering all possible grids using `5ew` to map

```
[a b c d e f g h i]

```

to

```
[[a b c d e]
 [b c d e f]
 [c d e f g]
 [d e f g h]
 [e f g h i]]

```

and then discarding the middle element and the middle element of each other element to get

```
[[a b d e]
 [b c e f]
 [d e g h]
 [e f h i]]

```

which are the four squares.
> 5 votes

# Answer
# Python2 ~~327~~ ~~271~~ ~~270~~ ~~263~~ 260 bytes

```
z,v,s={},3,range(1,10)
while len(z)<376:
 for i in range(8):v=hash(`v`);s[i],s[v%9]=s[v%9],s[i]
 m=map(lambda i:sum(s[i:i+5])-s[i+2],[0,1,3,4]);T=tuple(s)
 if all(x==m[0] for x in m) and not T in z:
  z[T]=1;print '%i %i %i\n'*3 % tuple(s[0:3]+s[3:6]+s[6:9])

```

## ------------

This is... not so short but it uses no libraries. This randomly permutes a square, checks it for magicness, prints it, and records it to prevent duplicates. After it has printed 376 unique magic squares, it stops.

I borrowed the Pseudo Random Number Generator from Keith Randall's entry for the golf named " Build a random number generator that passes the Diehard tests "

```
z,v={},3
def R(x,y):global v;v=hash(`v`);return v
while len(z)<376:
 s=sorted(range(1,10),cmp=R)
 m=[sum(q) for q in map(lambda p:s[p[0]:p[1]+1]+s[p[2]:p[3]+1], [[i,i+1,i+3,i+4] for i in [0,1,3,4]] )]
 if all(x==m[0] for x in m) and not tuple(s) in z.keys():
  z[tuple(s)]=1;print '%i %i %i\n'*3 % tuple(s[0:3]+s[3:6]+s[6:9])

```

De-golfed

```
# each magic square is an array of 9 numbers
#
#for example [1 9 3 7 2 5 6 4 8]
#
#represents the following square
#
#1 9 3
#7 2 5
#6 4 8
#
# to generate a random square with each number represented only once,
# start with [1 2 3 4 5 6 7 8 9] and sort, but use a random comparison
# function so the sorting process becomes instead a random permutation.
#
# to check each 2x2 subsquare for sums, look at the indexes into the
# array: [[0,1,3,4] = upper left,[1,2,4,5] = upper right, etc.
#
# to keep track of already-printed magic squares, use a dictionary
# (associative array) where the 9-element array data is the key.

from random import *
def magic(s):
 quads=[]
 for a,b,c,d in [[0,1,3,4],[1,2,4,5],[3,4,6,7],[4,5,7,8]]:
  quads+=[s[a:b+1]+s[c:d+1]]
 summ=[sum(q) for q in quads]
 same= all(x==summ[0] for x in summ)
 #print quads
 #print 'sum',summ
 #print 'same',same
 return same

magicsquares={}
while len(magicsquares.keys())<376:
        sq = sorted(range(1,10),key=lambda x:random())
        if magic(sq) and not magicsquares.has_key(tuple(sq)):
                magicsquares[tuple(sq)]=1
                print sq[0:3],'\n',sq[3:6],'\n',sq[6:9],'\n'

```
> 2 votes

# Answer
# Ruby 133

```
a=[]
[*1..9].permutation{|x|[0,1,3,4].map{|i|x[i]+x[i+1]+x[i+3]+x[i+4]}.uniq.size<2&&a<<x.each_slice(3).map{|s|s*' '}*'
'}
$><<a*'

'

```

Straightforward brute force approach. Test it here.
> 1 votes

# Answer
# J, 83 bytes

```
([:;@,(<LF),.~[:(<@(LF,~":)"1@#~([:*/2=/\[:,2 2+/@,;._3])"2)(3 3)($"1)1+!A.&i.])@9:

```

This is a function that outputs a string containing the 376 sturdy squares. Uses brute-force, generates all permutations of 1 thru 9, shape each into a 3x3 array, and filters it by checking if the sums of each 2x2 subarray are equal. Completes in half a second.

## Usage

```
   f =: ([:;@,(<LF),.~[:(<@(LF,~":)"1@#~([:*/2=/\[:,2 2+/@,;._3])"2)(3 3)($"1)1+!A.&i.])@9:
   $ f ''  NB. A function has to take something to be invoked,
           NB. but in this case it is not used by the function
   37 {. f ''  NB. Take the first 37 characters
1 5 3
9 8 7
4 2 6

1 5 6
8 7 3
4 2 9

   _38 {. f ''  NB. Take the last 38 characters
9 5 4
2 3 7
6 8 1

9 5 7
1 2 3
6 8 4

   NB. The output string ends with two newlines

```
> 1 votes

# Answer
# APL (Dyalog Extended), 38 bytes

```
s⌿⍨1=≢∘∪⍤1⍪+/,⍤⊢⌺1 2 2⊢s←3 3⍴⍤1⌂pmat 9

```

Try it online!

Uses the builtin `dfns.pmat` to generate required permutations.

Will add an explanation soon.

Made with golfing help from Adám, who also ran the program on his machine for checking. ↓

## Explanation

```
s⌿⍨1=≢∘∪⍤1⍪+/,⍤⊢⌺1 2 2⊢s←3 3⍴⍤1⌂pmat 9
                             1⌂pmat 9 matrix of permutations of 1..9
                      s←3 3⍴⍤         convert each to 3x3 matrix, and store in s
              ⊢⌺1 2 2⊢                get all overlapping 2x2 squares in each of those
        1⍪+/,⍤                        sum the flattened 2x2's of each
  1=≢∘∪⍤                              is there only 1 unique sum?
                                      this creates a bitmask for filtering each 3x3
s⌿⍨                                   filter s by that

```
> 1 votes

# Answer
# Jelly, 22 bytes

```
9Œ!s€3+Ɲ€Z$⁺FEƲƇG€j⁾¶¶

```

Try it online!

*Very* inefficient. Times out on TIO, and takes around 4m30s on my local computer. Uses Dennis' method for finding the sums of the 2x2 submatrices. The last 6 bytes could be removed if the output format was more permissive. Outputs in the same order as in the question.

## How it works

```
9Œ!s€3+Ɲ€Z$⁺FEƲƇG€j⁾¶¶ - Main link. No arguments
9Œ!                    - Yield all permutations of [1, 2, 3, 4, 5, 6, 7, 8, 9]
   s€3                 - Split each into a 3x3 matrix
              ƲƇ       - Keep those for which the following is true:
       Ɲ€              -   Over each neighbouring pair in each row:
      +                -     Take the sum
         Z             -    Transpose
          $⁺           -    Do this again
            F          -    Flatten
             E         -    Are all elements equal?
                G€     - Join each row by spaces and then join rows by newlines
                  j⁾¶¶ - Join the final matrices with two newlines

```
> 0 votes

# Answer
# Japt, 34 bytes

+9 bytes for the output formatting :\

```
9õ á mò3 kÈ®ä+ÃÕ®ä+Ãrâ ÊÉÃ®m¸·ÃqR²

```

Try it
> 0 votes

---
Tags: code-golf, number, arithmetic, number-theory, grid
---


title: Find the syncopation

text:
# Question
Title: Find the syncopation
Given an input of a string consisting entirely of `q`s representing quarter notes and `e`s representing eighth notes, output the indices of the quarter notes that are syncopated.

Syncopation is complex, but for the purposes of this challenge, our definition of "syncopated" will be very simple: a quarter note that starts on the "off-beat"—that is, the beats counted as "and" in n/4 time.

This may alternatively be defined as any quarter note that is preceded by an odd number of eighth notes. For example, the notes marked with `*` below are considered syncopated, and their indices are also shown:

```
eqqeqqeqqe
 **    **
 12    78
Output: 1 2 7 8

```

The input will always consist of a whole number of measures in 4/4 time (a quarter note is a quarter of a measure, and an eighth note is an eighth of a measure). (The input will also never be empty.) Output can either be a single string with elements separated by any delimiter that does not contain numbers or an array/list/etc. The output may be 1-based (i.e. the first index is 1 instead of 0) if you wish, and it may also be in any numeric base (unary, decimal, etc.).

Since this is , the shortest code in bytes wins.

Test cases:

```
In                        Out
-----------------------------------------------
eqqqe                     1 2 3
qeqeq                     2
qqqeqqeeeeqeqeqeqqeqqeqq  4 5 10 14 19 20
eeeeeqeeqeeqqqqeqeqeeqe   5 8 11 12 13 14 18 21
qqqq                      <none>
eeeeeeee                  <none>

```

# Answer
# Jelly, ~~12~~ 9 bytes

```
=“e”µ<^\O

```

As a program, the above code requires quotes around the input. Since that is not allowed, this is a function submission. The output is 1-based. ~~Try it online!~~

### How it works

```
=“e”µ<^\O    Monadic link. Argument: s (string)

=“e”         Check each character for equality with 'e'. Yields a Boolean array.
    µ        Start a new, monadic chain.
      ^\     Compute the array of partial reductions by XOR, i. e., the parities
             of all prefixes of the Boolean array.
     <       Check if the Booleans are strictly smaller than the parities.
             A truthy outcome indicates an off-beat quarter note.
        O    Yield all indices of 1's.

```

### Update

The above code doesn't work anymore in the latest version of Jelly, since we need a *character* **e**, but `“e”` yields a string. Fixing that saves a byte, for a total of **8 bytes**.

```
=”eµ<^\O

```

This works as a full program. Try it online!
> 12 votes

# Answer
# Ruby, 46

```
i=e=0
gets.bytes{|n|e^=n
e&4|n>114&&p(i)
i+=1}

```

Input to stdin. Output to stdout, newline separated.

Commented

```
i=e=0               #i keeps index, e keeps track of 8ths.
gets.bytes{|n|      #iterate through bytes in the input
e^=n                #xor e with input. We're interested in the 4's bit, which is only affected by ascii e, not ascii q
e&4|n>114&&p(i)     #e&4 evaluates to 4 or 0. OR with n and if the value is greater than ascii code for q, print index
i+=1}               #increment index

```
> 7 votes

# Answer
# JavaScript ES7, ~~50~~ 48 bytes

Pretty short for JS, if you ask me. `[for...of]` syntax, basically combined map and filter, comes in handy for this challenge.

```
s=>[for(c of(i=f=0,s))if(++i&&c>'e'?f%2:f++&0)i]

```

Defines an anonymous function that outputs a 1-indexed array.

### Test snippet

This uses an ungolfed, un-ES7'd version of the code.

```
a = function(s) {   // Create a function a that takes in a parameter s and does these things:
  var r = [],       // Set variable r to an empty array,
  i = 0, f = 0;     // i to 0, and f to 0.
  for(c of s) {     // For each character c in s:
    i++;            //  Increment i by 1.
    if(             //  If
      c == 'q' ?    //   if c == 'q',
      f%2 === 1 :   //    f is even; otherwise,
      f++ && false) //    increment f and don't execute this:
      r.push(i);    //   Add i to the end of r.
  } return r;       // Return r.
}
```

```
<input type="text" value="eqqqe" id=O />
<button onclick="P.innerHTML='['+a(O.value)+']'">Try it</button>
<p id=P />
```
> 6 votes

# Answer
# MATL, 12 ~~14~~ ~~16~~ bytes

```
j101=tYs2\<f

```

*Thanks to Dennis for removing 2 bytes (and for hosting MATL in his awesome online platform!)*

This uses current version (9.3.0) of the language/compiler.

Input and output are through stdin and stdout. The result is 1-based.

**Example**:

```
>> matl j101=tYs2\<f
> eeeeeqeeqeeqqqqeqeqeeqe
6  9 12 13 14 15 19 22

```

Or **try it online!**

## Explanation

```
j             % input string
101=          % vector that equals 1 at 'e' characters and 0 otherwise
t             % duplicate
Ys2\          % cumulative sum modulo 2
<             % detect where first vector is 0 and second is 1
f             % find (1-based) indices of nonzero values

```
> 5 votes

# Answer
## J, ~~20 19~~ 17 bytes

```
=&'e'(I.@:<~:/\@)

```

Thanks to randomra for saving a byte, and to Dennis for saving two. This is an unnamed monadic verb, used as follows:

```
  f =: =&'e'(I.@:<~:/\@)
  f 'eqqqe'
1 2 3

```

Try it here.

## Explanation

```
=&'e'(I.@:<~:/\@)
=&'e'               Replace every 'e' with 1, other chars with 0
     (         @)   Apply the verb in parentheses to the resulting 0-1 vector
           ~:/\     Cumulative reduce with XOR (parity of 'e'-chars to the left)
          <         Element-wise less-than with original vector
      I.@:          Positions of 1s in that vector

```
> 5 votes

# Answer
# GNU grep, ~~3+17=20~~ 3 + 15 = 18 bytes

The program requires the options `boP`. The code is

```
q(?!(q|eq*e)*$)

```

Save it as `synco`, then run as `grep -boPf synco`.

The output separator is `:q` followed by a newline. E.g. the output for `eqqqe` is

```
1:q
2:q
3:q

```

The meanings of the flags are:

* `P`: Use PCRE regexes.
* `o`: This means to print only the part of the line that matches the regular expression, but that's not why it's important. `o` is used because it has the effect of allowing multiple matches per line.
* `b`: Print the offset in bytes of the beginning of each match from the beginning of the file.

The pattern checks that there is not an even number of eighth notes after a quarter note.
> 5 votes

# Answer
# Python 2, ~~94~~ ~~85~~ ~~79~~ ~~75~~ 66 bytes

**EDIT:** Thanks Doorknob and Alex A.

**EDIT:** Thanks Alex A.

**EDIT:** Now using input() so the input must be a string with the quotes.

**EDIT:** Thanks Zgarb for recommending me to use enumerate.

Simply counts number of e's and if q, check if e count is odd, then print index.

```
e=0
for j,k in enumerate(input()):
 if"q">k:e+=1
 elif e%2:print j

```

Try it here
> 3 votes

# Answer
## Haskell, ~~58~~ 51 bytes

```
f x=[i|(i,'q')<-zip[0..]x,odd$sum[1|'e'<-take i x]]

```

Usage example: `f "eeeeeqeeqeeqqqqeqeqeeqe"` -\> `[5,8,11,12,13,14,18,21]`.

Go through the list and output the current index `i` for every char `'q'` if there's an odd number of `'e'`s before it.
> 3 votes

# Answer
# APL (Dyalog Classic), 12 bytes

```
(⍸~×≠\)'e'∘=

```

Try it online!

Outputs 1-indexed.

### Explanation:

```
       'e'∘=    ⍝ Map each element to whether it is equal to 'e'
(     )         ⍝ Then apply the train
  ~             ⍝ Not the array into indexes of 'p'
   ×            ⍝ Multiply this by
    ≠\          ⍝ The cumulative reduction by inequality
 ⍸              ⍝ And get the indexes of the ones in the array

```
> 3 votes

# Answer
# Python 3, ~~109~~ ~~95~~ ~~80~~ ~~90~~ ~~88~~ ~~76~~ ~~68~~ ~~67~~ ~~66~~ 64 bytes

Counts the number of `q`s and `e`s and adds the index of the current `q` if the number of preceding `e`s is odd.

**Edit:** Now it prints a list of the indices of s that are `q` and have an odd number of `e`s preceding them. Eight bytes saved thanks to Doorknob and two more thanks to feersum.

```
lambda s:[x for x,m in enumerate(s)if("e"<m)*s[:x].count("e")%2]

```

**Ungolfed:**

```
def f(s):
    c = []
    for index, item in enumerate(s):
        if item == "q":
            if s[:index].count("e")%2 == 1:
                c.append(index)
    return c

```
> 2 votes

# Answer
# JavaScript ES6, ~~63~~ ~~60~~ 58 bytes

```
x=>[...x].map((e,i)=>e>'e'?n%2&&a.push(i):n++,a=[],n=0)&&a

```

Anonymous function that outputs an array. Thanks to user81655 for saving two bytes. Here is an ungolfed version that uses better supported syntax.

```
f=function(x) {
  a=[] // Indeces of syncopated notes
  n=0 // Number of e's encountered so far
  x.split('').map(function(e,i) { // For each letter...
    e>'e'? // If the letter is q...
      n%2&& // ...and the number of e's is odd...
        a.push(i): // ...add the current index to the array
      n++ // Otherwise, it is e so increment the counter
  })
  return a
}

run=function(){document.getElementById('output').textContent=f(document.getElementById('input').value)};document.getElementById('run').onclick=run;run()
```

```
<input type="text" id="input" value="qqqeqqeeeeqeqeqeqqeqqeqq" /><button id="run">Run</button><br />
<samp id="output"></samp>
```
> 2 votes

# Answer
## Minkolang 0.15, 28 bytes

```
(o"q"=7&z1+$z8!z2%,2&iN$I$).

```

Try it here.

### Explanation

```
(                        Open while loop
 o                       Read in character from input
  "q"                    Push the character "q"
     =                   1 if the top two items on stack are equal, 0 otherwise
      7&                 Pop and jump 7 spaces if truthy

        z                Push register value on stack
         1+              Add one
           $z            Pop top of stack and store in register
             8!          Jump eight spaces

        z                Push register value on stack
         2%              Modulo by 2
           ,             boolean not
            2&           Pop and jump two spaces if truthy
              i          Push loop counter
               N         Output as number

                $I       Push length of input
                  $).    Close while loop when top of stack is 0 and stop.

```
> 2 votes

# Answer
# C (function), 65

Thanks to @Dennis for the extra golfing!

```
i,n;f(char*m){for(i=n=0;*m;i++)*m++&4?++n:n%2?printf("%d ",i):0;}

```
> 2 votes

# Answer
# Mathematica, 76 bytes

```
Flatten[Range[#+1,#2-1]&@@@StringPosition[#,"e"~~"q"..~~"e",Overlaps->1<0]]&

```

Something interesting I noticed. All of the syncopated parts are of form `eqqq..qqe`, so I just detect those and give the indices of the `q`s.
> 1 votes

# Answer
# Japt, ~~29~~ ~~23~~ 21 bytes

Not non-competing anymore!

```
0+U ¬®¥'e} å^ ä© m© f

```

Try it online!

### How it works

```
         // Implicit: U = input string, e.g.    "eqqeqeq"
0+U      // Add a 0 to the beginning.           "0eqqeqeq"
¬        // Split into chars.                   ['0,'e,'q,'q,'e,'q,'e,'q]
®¥'e}    // Map each item X to (X == 'e).       [F, T, F, F, T, F, T, F]
å^       // Cumulative reduce by XOR'ing.       [0, 1, 1, 1, 0, 0, 1, 1]
ä©       // Map each consecutive pair with &&.  [0, 1, 1, 0, 0, 0, 1]
m©       // Map each item with &&. This performs (item && index):
         //                                     [0, 1, 2, 0, 0, 0, 6]
f        // Filter out the falsy items.         [   1, 2,          6]
         // Implicit output                     [1,2,6]

```

### Non-competing version, 18 bytes

```
U¬m¥'e å^ ä©0 m© f

```

Try it online!
> 0 votes

# Answer
# Befunge, 43 bytes

```
:~:0\`#@_5%2/:99p1++\>2%#<9#\9#.g#:*#\_\1+\

```

Try it online!

**Explanation**

We start with two implicit zeros on the stack: the note number, and a beat count.

```
:               Make a duplicate of the beat count.
~               Read a character from stdin.
:0\`#@_         Exit if it's less than zero (i.e. end-of-file).
5%2/            Take the ASCII value mod 5, div 2, translating q to 1 and e to 0.
:99p            Save a copy in memory for later use.
1+              Add 1, so q maps to 2 and e to 1.
+               Then add that number to our beat count.
\               Get the original beat count that we duplicated at the start.
2%              Mod 2 to check if it's an off-beat.
99g*            Multiply with the previously saved note number (1 for q, 0 for e).
_               Essentially testing if it's a quarter note on an off-beat.
       \.:\     If true, we go turn back left, get the beat count, and output it.
         >2     Then push 2 onto the stack, and turn right again.
2%              That 2 modulo 2 is just zero.
99g*            Then multiplied by the saved note number is still zero.
_               And thus we branch right on the second pass.
\1+\            Finally we increment the note number and wrap around to the start again.

```
> 0 votes

# Answer
# Japt, 11 bytes

```
ðÈø¬?Tu:!°T

```

Try it
> 0 votes

---
Tags: code-golf, music
---


title: Generate the Temple Skyline Sequence

text:
# Question
Title: Generate the Temple Skyline Sequence
Consider the following process:

1. Take some non-negative integer N.

e.g. N = `571`
2. Express it in binary with no leading zeroes. (Zero itself is the only exception, becoming `0`.)

e.g. `571` = `1000111011` in binary
3. Break apart consecutive runs of ones and zeroes in this binary representation.

e.g. `1000111011``1`, `000`, `111`, `0`, `11`
4. Sort the runs from longest to shortest.

e.g. `1`, `000`, `111`, `0`, `11``000`, `111`, `11`, `1`, `0`
5. Overwrite all the digits in each run with alternating `1`'s and `0`'s, always starting with `1`'s.

e.g. `000`, `111`, `11`, `1`, `0``111`, `000`, `11`, `0`, `1`
6. Concatenate the result to get a new binary number.

e.g. `111`, `000`, `11`, `0`, `1``1110001101` = `909` in decimal

When you plot the values produced by this process you get a pretty neat graph:

And it's hopefully apparent why I'm calling the resulting sequence the *Temple Skyline sequence*:

# Challenge

Write a program or function that takes in a non-negative integer N and prints or returns the corresponding Temple Skyline sequence number. Your input and output should both be in decimal.

e.g. If the input is `571` the output should be `909`.

**The shortest code in bytes wins.**

For reference, here are the terms in the sequence from N = 0 to 20:

```
0   1
1   1
2   2
3   3
4   6
5   5
6   6
7   7
8   14
9   13
10  10
11  13
12  12
13  13
14  14
15  15
16  30
17  29
18  26
19  25
20  26

```

Here are the terms from 0 to 1023.

# Answer
# Pyth, ~~20~~ 19 bytes

```
ACr.BQ8|is*V_SGH2 1

```

*1 byte saved by Jakube*

Test Suite

Uses the fact that after run-length-encoding, the runs are the desired runs in the output.

Lost 3 bytes special casing 0.
> 4 votes

# Answer
# CJam, ~~25~~ ~~23~~ 22 bytes

```
ri1e>2be`z($W%a\+ze~2b

```

Just a bit of run-length encoding. -1 thanks to @MartinBüttner.

Try it online / Test suite.

### Explanation

```
ri        Read n from input as int
1e>       Take max with 1 (special case for n = 0)
2b        Convert n to binary
e`        Run length encode
z         Zip, giving a pair [<counts> <10101.. array>]
($W%      Drop the counts array and sort decending
a\+z      Add it back to the 10101.. array and re-zip
e~        Run length decode
2b        Convert from binary

```
> 14 votes

# Answer
# Pyth - ~~21~~ 20 bytes

*Thanks to @sok for saving me one byte!*

```
is.em%hk2hb_Sr.BQ8 2

```

Try it here online.
> 11 votes

# Answer
# Python 2, 121 bytes ~~125~~

121: Thanks to Sp3000 for shaving off 4 bytes!

```
import re;print int("".join(n*`~i%2`for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)

```

125

```
import re;print int("".join("10"[i%2]*n for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)

```
> 6 votes

# Answer
# JavaScript ES6, 110 bytes ~~113~~ ~~116~~ ~~119~~ ~~120~~

*Saved 3 bytes thanks to @intrepidcoder*

*Saved 3 bytes thanks to @NinjaBearMonkey*

```
n=>+('0b'+n.toString(2).split(/(0+)/).sort((b,a)=>a.length-b.length).map((l,i)=>l.replace(/./g,i-1&1)).join``)

```

Straight forward approach. Don't like the length of the sort function but I can't think of a way to golf it.
> 5 votes

# Answer
# C++, ~~535~~ 527 Bytes

(thanks zereges for shaving off some bytes.)

Now that we got rid of those bytes the program is now competetive ;)

```
#include<iostream>
#include<cmath>
int main(){int I,D;std::cin>>I;while(I>int(pow(2,D))){D++;}int L[99];int X=0;int Z=0;int O=0;for(int i=D-1;i>=0;i--){if( int(pow(2,i))&I){if(Z>0){L[X]=Z;Z=0; X++;}O++;}else{if(O>0){L[X] = O;O=0;X++;}Z++;}}if(Z>0){L[X]=Z;Z=0;X++;}if(O>0){L[X]=O;O=0;X++;}int P=0;bool B = true;int W = D-1;for(int j=0;j<X;j++){int K=0;int mX=0;for(int i=0;i<X;i++){if(L[i]>K){K=L[i];mX=i;}}L[mX]=0;if(B){for(int k=0;k<K;k++){P+=int(pow(2,W));W--;}}else{for(int k=0;k<K;k++){W--;}}B^=1;}std::cout<<P;return 0;}

```

I'm new to golfing, so **please give me some tips in the comments**.

Things like "you don't need those brackets" or "use printf" are all helpful, but I also appreciate advice on the logic. Thanks in advance!

For ease of reading, I present the ungolfed version:

```
#include<iostream>
#include<cmath>
int main()
{
int input,digits;

std::cin>>input;
while(input > int(pow(2,digits))){digits++;}

int list[99];
int index=0;
int zCounter=0;
int oCounter=0;

for(int i=digits;i>0;i--)
{
    if( int(pow(2,i-1))&input)
    {
        if(zCounter>0)
        {
            list[index] = zCounter;
            zCounter=0;
            index++;
        }
        oCounter++;
    }
    else
    {
        if(oCounter>0)
        {
            list[index] = oCounter;
            oCounter=0;
            index++;
        }
        zCounter++;
    }
}
if(zCounter>0)
{
        list[index] = zCounter;
        zCounter=0;
        index++;
}
if(oCounter>0)
{
        list[index] = oCounter;
        oCounter=0;
        index++;
}

int output = 0;
bool ones = true;
int power = digits-1;
for(int j=0;j<index;j++)
{
    int max=0;
    int mIndex=0;
    for(int i=0;i<index;i++)
    {
        if(list[i]>max){max=list[i];mIndex=i;}
    }
    list[mIndex]=0;

    if(ones)
    {
        for(int k=0;k<max;k++)
        {
            output+=int(pow(2,power));
            power--;
        }
    }
    else
    {
        for(int k=0;k<max;k++)
        {
            power--;
        }
    }
    ones^=1;

}
std::cout<<output;
return 0;
}

```

**EDIT** golfed version brought down a couple bytes, ungolfed version unchanged
> 5 votes

# Answer
# Perl 5.10, 121 101

```
say oct"0b".join'',map{$|=1-$|;$_=~s/./$|/gr}sort{length$b<=>length$a}(sprintf"%b",shift)=~/(0*|1*)/g

```

I think the sort part can be shorter.

Edit: -20 bytes, thanks to symbabque!
> 3 votes

# Answer
# Haskell, ~~132~~ 131 bytes

```
import Data.List
g 0=[]
g n=mod n 2:g(div n 2)
q=[1]:[0]:q
f=foldl((+).(2*))0.concat.zipWith(<*)q.sortOn((-)0.length).group.g.max 1

```

Usage example:

```
> map f [0..20]
[1,1,2,3,6,5,6,7,14,13,10,13,12,13,14,15,30,29,26,25,26]

```

How it works:

```
                 max 1         -- fix n=0: f(0) is the same as f(1)
               g               -- turn into binary, i.e. list of 0s and 1s
            group              -- group sequences of equal elements
         sortOn((-)0.length)   -- sort groups on negative length
      zipWith(<*)q             -- map each element in a group to constant 1 or 0 by turns
   concat                      -- flatten all groups into a single list
foldl((+).(2*))0               -- convert back to decimal

```
> 2 votes

# Answer
# J - 30 bytes

Function taking integer on right. Correctly handles 0.

```
(\:~#2|#\)@(#;.1~1,2~:/\])&.#:

```
* `#:` \- Take the binary representation.
* `1,2~:/\]` \- Between each digit, report *True* if they are different. Prepend a *True* so that the list has *True* at the start of each "run".
* `(#;.1~...)` \- Using the boolean vector above, take the length of each run.
* `\:~` \- Sort these lengths from longest to shortest.
* `2|#\` \- Take a list of alternating `1 0 1 0 ...` as long as the list of lengths.
* `(...#...)` \- For each number on the left (sorted lengths), take as many of the corresponding item on the right (alternating 1's and 0's)
* `&.` \- Convert this new binary representation back to a number.

Examples:

```
   (\:~#2|#\)@(#;.1~1,2~:/\])&.#: 571
909
   i.21   NB. zero to twenty
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
   (\:~#2|#\)@(#;.1~1,2~:/\])&.#: every i.21   NB. apply separately to every number
1 1 2 3 6 5 6 7 14 13 10 13 12 13 14 15 30 29 26 25 26

```
> 2 votes

# Answer
# Python 3, ~~146~~ 136 bytes

```
import re;print(int(''.join(len(j)*'01'[i%2<1]for i,j in enumerate(sorted(re.findall('1+|0+',bin(int(input()))[2:]),key=len)[::-1])),2))

```
> 1 votes

# Answer
# Mathematica, 83 bytes

```
Flatten[0#+(d=1-d)&/@SortBy[d=0;Split[#~IntegerDigits~2],-Length@#&]]~FromDigits~2&

```

This defines an unnamed function.
> 1 votes

# Answer
# Ruby, ~~107~~ ~~104~~ 102 bytes

(saved 3 bytes thanks to **nimi**)

Not going to beat the likes of CJam, but I got it pretty small for a sane language.

```
p gets.to_i.to_s(2).scan(/((.)\2*)/).map{|e|e[i=0].size}.sort.reverse.map{|e|"#{i=1-i}"*e}.join.to_i 2

```
> 0 votes

# Answer
## Java 8, ~~179~~ 176 bytes

```
(x)->{int g[]=new int[32],h=0,i=highestOneBit(x);g[0]=1;while(i>1)g[((x&i)>0)^((x&(i>>=1))>0)?++h:h]++;sort(g);for(i=32,h=0;g[--i]>0;)while(g[i]-->0)h=h<<1|i%2;return x<1?1:h;}

```

I used two static imports: `java.util.Integer.highestOneBit` and `java.util.Arrays.sort`.

For readability, here's the code ungolfed:

```
java.util.function.ToIntFunction<Integer> f = (x) -> {
  int g[] = new int[32], h = 0, i = java.util.Integer.highestOneBit(x);
  g[0] = 1;
  while (i > 1) {
    g[((x & i) > 0) ^ ((x & (i >>= 1)) > 0) ? ++h : h]++;
  }
  java.util.Arrays.sort(g);
  for (i = 32, h = 0; g[--i] > 0;) {
    while (g[i]-- > 0) {
      h = h << 1 | i % 2;
    }
  }
  return x < 1 ? 1 : h; // handle zero
};

```
> 0 votes

# Answer
# Husk, 11 bytes

```
ḋ`Ṙİ¬↔OmLgḋ

```

Try it online!
> 0 votes

# Answer
# Japt, 14 bytes

```
¤ò¦ ñÊÔËîEvÃ¬Í

```

Try it

```
¤ò¦ ñÊÔËîEvÃ¬Í     :Implicit input of integer
¤                  :To binary string
 ò                 :Partition on
  ¦                :Inequality
    ñ              :Sort by
     Ê             :Length
      Ô            :Reverse
       Ë           :Map each D at 0-based index E
        î          :  Fill D with
         Ev        :  Parity of E
           Ã       :End map
            ¬      :Join
             Í     :To decimal

```
> 0 votes

# Answer
# APL (Dyalog Extended), <sup>~~32~~</sup> 30 bytes

```
⊥{⍵/(≢⍵)⍴⊤2}⊃¨∨{⍴¨⍵⊂⍨1,2≠/⍵}⊤⎕

```

Try it online!

-2 bytes for full program.

## Explanation

```
⊥{⍵/(≢⍵)⍴⊤2}⊃¨∨{⍴¨⍵⊂⍨1,2≠/⍵}⊤⎕
                            ⊤⎕ convert input to binary
                       2≠/⍵    inequality of overlapping pairs
                     1,        prepend 1
                  ⍵⊂⍨          partition bits on that
                ⍴¨             get length of each part
              ∨                sort in descending order
            ⊃¨                 unenclose each
          ⊤2                   array [1,0]
    (≢⍵)⍴                      reshape to ⍵'s length
  ⍵/                           filter ⍵ by that(every other element)
⊥                              convert that back to binary

```
> 0 votes

# Answer
# Jelly, 13 bytes

```
BŒgLÞṚJḂṁ"ƊFḄ

```

Try it online!

## How it works

```
BŒgLÞṚJḂṁ"ƊFḄ - Main link. Takes n on the left
B             - Convert to binary
 Œg           - Group adjacent equal elements; Call this l
    Þ         - Sort by...
   L          -   length
     Ṛ        - Reverse, to put the longest first
          Ɗ   - Run the previous 3 commands over the sortedt list
      J       - Yield [1, 2, ..., len(l)]
       Ḃ      - Bit;  [1, 0, 1, 0, ..., len(l)%2]
         "    - Zip with l and do the following over each pair
        ṁ     -   Mould 1 or 0 to each element of l
           F  - Flatten
            Ḅ - Convert from binary

```
> 0 votes

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


# Question
Title: Shortest "arithmetic" formula to output 1000 primes
Write a formula using only the digits `0-9`, `+`, `*`, `-`, `/`, `%` and `^` to output a 1000 *distinct* primes when given input (which can be used as a variable `n` in the formula) of numbers 1 to 1000. (Note that `/` will give the quotient as all arithmetic is integer arithmetic.) Solutions can use `(` and `)` freely and they will not be counted in the length.

The shortest formula wins! The primes only need to be *some* 1000 primes not necessarily the first 1000.

**EDIT**

Edited for clarity based on suggestions by Sisyphus and an earlier question on primality testing.

Symbols are meant to work with integers in the "usual" way as follows.

`n` : Represents a number from 1 to 1000 which is the "input" to the formula. It can be used any number of times in the formula and it will represent the same input.

`0-9` : Sequences of digits (terminated by non `0-9` symbols or ) return the number represented by this decimal representation. Negation of an expression can be represented as `(-`{expression}`)`

`+` : Returns the sum of two numbers

`*` : Returns the product of two numbers

`/` : Returns the integer quotient of two numbers

`%` : Returns the remainder on division of the first number by the second number. This and `/` follow Euclidean division conventions.

`-` : Returns the result of subtracting the second number from the first number.

`^` : Returns the power of the first number by the second number. Anything to the power 0 is taken as 1 including 0!

`()` : Brackets are used in pairs to encapsulate an expression that returns a number using the previous rules.

# Answer
> 17 votes
# Score ~~1164~~ ~~883~~ ~~835~~ ~~772~~ ~~601~~ ~~574~~ ~~554~~ 506

```
541^n*743^(n/2)*(-1)^(n/4)*17^(n/8)%2310+297999352693782350435634574256421873511169209139789986107407037031463672744907435566931682004950168827622126589004268258979810886896053712313147567393521260370898856430728936238509646240927399434529133911694916958518274696252190810912239170743768597920487389824644988723446125401158124982957878348425345764310640796665180984553241724855646631162669954988652785474199384658696484753453854147610893664426900411229033105555630617039087023847065224114331551958/67^(n%250)%67*2310

```

Try it online!

(OP hasn’t answered my question about the behavior of `/` and `%` on negative numbers, so this answer works under the floored or Euclidean conventions where `(-1) % 2310 = 2309`.)

# Answer
> 17 votes
# Score ~~424~~ 193

```
(30*n+(1-(1/(2^(n*30+16)%(n*30+17))))*((1-(1/(2^(n*30+22)%(n*30+23))))*((1-(1/(2^(n*30+28)%(n*30+29))))*((1-(1/(2^(n*30+12)%(n*30+13))))*((1-(1/(2^(n*30+6)%(n*30+7))))*((1-(1/(2^(n*30+40)%(n*30+41))))*((1-(1/(2^(n*30+18)%(n*30+19))))*(882)-22)+34)-6)-16)+6)+6)+17)+(1/(1+(n-475)^2))*10

```

This code searches the first Fermat pseudoprime of the form `n*30+d`, with offset d from `{17,23,29,13,7,11,19,1}`. The 4 cases where this fails (nothing found or pseudoprime found that is not a prime) are fixed a posteriori.

The order in which the offsets are testet was handcrafted as to minimize the number of pseudoprimes.

The following building blocks where used to yield boolean values: `1/t` yields the truth value of `t==1` (when we know that `t` is positive), `1/(1+(n-t)^2)` yields the truth value of `n==t`.

`b1*t1+(1-b1)*( b2*t2+(1-b2)*( b3*t3+(1-b3)*(...)))` mimics the code

```
if b1: t1
else if b2: t2
else if b3: t3
...

```

**Edit**: I could't resist to optimize. Key tricks:

* the if-else now returns only the offset, the final result is call afterwards.
* xnors latest if-else gadget vastly reduced code size
* the resulting nested expression had adjacend summands that could be contracted
* no Fermat test for the last index, as on failure it must be corrected anyway
* grid offsets reduced the number of faulty cases to 1

Verification program Generator program

# Answer
> 14 votes
# Score ~~163~~,162

```
1%(4^(n*15+701)%(n*30+1403))*(1%(2^(n*30+28)%(n*30+29))*(1%(4^(n*15+6)%(n*30+13))*(1%(4^(n*15+9)%(n*30+19))*(1%(4^(n*15+5)%(n*30+11))*(1%(2^(n*30+6)%(n*30+7))*(1%(2^(n*30)%(n*30+1))*(16)-6)-4)-8)+6)-16)-1374)+n*30+1403

```

Verification, generation code (takes around 20 seconds to run)

I would have posted this as a comment, except I only have 1 reputation

This answer is based on Max Kubierschky's solution, with many of xnor's improvements (specifically everything in his generation program with the addition of his trick to shorten expressions within powers).

The main optimization is based on Max Kubierschky's comment, and I found offsets `(1403, 29, 13, 19, 11, 7, 1, 17)` which are mostly small (with the exception of 1403) and have no faulty cases (these are just the previous offsets + 30).

## Explanation

This method works by generating primes of the form `30*n+(30*k+o)` where `30*k+o` is the offset composed of o, the base offset from the set `{1,7,11,13,17,19,23,29}` and k, the grid offset in the range -1 to infinity. The grids are the sets of integers n from 1 to 1000 for which `30*(k+n)+o` satisfies the Fermat test for base 2. The prime grids are the sets of integers n from 1 to 1000 for which `30*n+(30*k+o)` is prime.

The grid offsets were generated by first considering only prime grids (ignoring possible faulty cases) in order to find a set of grid offsets to cover the numbers from 1 to 1000, (in this case they were found by setting all except one of the grid offsets to 0, and varying the remaining grid offsets in the range from -1 to 66)

After finding grid offsets that cover the set, the code runs through all the permutations of offsets to find an order of offsets that covers up all the faulty cases (for the offsets used in the current formula, there are 81 that work), and then generating the formula using each to find which one turns out smallest

# Answer
> 11 votes
# Score 2341

This outputs all primes between \\$31\\$ and \\$8017\\$ (included).

```
(113467395935668970410160492737179506361846013862444084170197806945186405092696909126164158205176795679626257477170011681151081828693721528545308301463032313852735898720278373462178435545407324698821351304548663895918208828677426209417450978147368548225197577994423342074325769235860896833550745001703798952436205556087566508085462913775782980107289038262897153290911775461849717826677653709482106939563942394004153958440037041024098156603769869491411749714891362691603370984320936124882165280605174558859749487518953604842331779664328074931195219441658740089199947350409773050270253672458490842517716227535564556430387611590820439097600165832489226127768727315594781312368235772273799332206758908020271761747844563774441691210056862686595288936465304647859214996600265632129456351742413141396515373657806301978324762068082957610010981667490015017872109960968210719664738068557705903476757448731528153247317383397296951323720188125875523771873472067739298722926939700395850510069970848932566438053043914675253394668929358649440219868955587507427792258737478621439222869420782804120723724037942099140240986671113771843292946536125599661698395893047644516938416344212452574005345276922734768543821803294119263624051859444984143612848763146503016281898460776934493046854691490177334701465551154370051389269555217280444180285443508781807182786653180547028418689044382239111057385640034581765695611964566960423155654254631533264137376719604736646235721281638954806708051896372829794828522441565514326091912749474754904829505420000828614379978905433227551134966163328596138390836978449350464146519410700211096728982452219157828903470370081269726761212190236152174162025868830122533316205222356743692764196532590297434905214324476315471045728469350713970766245611550719074621408922145054478879292926089731205325210583591485438579344315785755440427094785080423582680705622279978441230497635622038519006130677863238128994042483893669828145180491933002965357145427263569009059259792273674006429955369804616413369843446578638589803530417606529429534136839003463278401805099943786536199970623822629008628461486362852575470843011844101058219237624888472496428195993935156341808156330726437453034634118080653972710684434727685175583816599255076497400463324245086662776394809313991656593421958024921754700582702681454016857120679602782/(208^(n-1))%208)*2-389+n*8

```

Try it online! (Node.js)

### How?

We compute:

$$a(n)=d(n)\times 2-389+8n$$

with \\$0\le d(n)\<208\\$.

The values of \\$d(n)\\$ are extracted from a large integer, using base \\$208\\$.

Below is a graphical representation of \\$d(n)\\$. The minimum is reached at \\$n=399\\$, for which we directly have \\$a(399)=8\times 399-389=2803\\$.

# Answer
> 8 votes
# Score ~~1778~~ ~~1319~~ 1164

-459 inspired by Neil's suggestions!

```
(28389416454731914904646197269110195258968918334324648337536406183122452341375087148095278619811035121264892162819521481008101705277372014120459537607320900170581458493476732106029764703970199356551116634482447603151892501883985471668745077729919867085592433543835805593713705073935219732297479335704578859520285745463599513991638068362975801056573234819165907183812641577379596655404026370719245188577913240916435487946831490476753322022399310328082542064590520714793222945825868990061383486920959013849054510725156607978917228480666383141633344797723352686825873369593489365635288158535711600587674466307031798274562517630853907709405080966507256977400682764885616947585079339593770144096628672186322100621135207302538190833576961188067354198288862669754543325834368496102584439249310678425485967421525911011440604945657742285226023738594503000443799738987162853276495354222398842865644351430245057910519732921873667017428523263018326208740011108682459267993023371456176948637898475810086660149605871207027333515638814123020249096374464098648830557815605475878366999652657721355174060931879798441836550660645385542381428064142926776728816247052/(14^(n-1))%14+17*n)*6-1

```

Verification program, Generator program

This only considers primes of the form \\$6k-1\\$, and yields the lowest such prime larger or equal then \\$102n-1\\$.

---

# Score ~~1635~~ ~~1604~~ 1572

The rules don't explicitly forbid this, but it I'm not sure if this is intended. Similar to the above, but finds the next prime after \\$\lfloor n^{1007 \over 621} \rfloor\\$.

```
16921707110807543794883034080662369959145330548686331531608873466161289588508225504395036067059456808254955842748011935275567235182962066696532824341658478313282515740212407513889626921371569995949618530076057857935444678903541507451833650971208966857022879588416744784446458319742198436165114149099979782639487537376816458053319371322652945071076875723112404278546530735706274859341438493065587724231536852995916148117098900150719957460662049351379626720184420298531075385276847667099516667910747707987556366430526973567431116704034575028503641091403375164564764095445312182120994347975065105984011801750777939791614004132127064169527985645152866679765959804131578103751126570294714529430395223496169502308685883689716858687150949295161789378929626842080159238203320971831181073359220269422355146095712138282898528757872049694061460608989183240128781928642651093781146703726149529559745625017336481225823115996890606949461379145867395915059579445847541041812545106491388887871854979774599921555206338249335536406513747513391059876604297546812682955845160908578873034957552441194311592692169821206761814295401029352512438888121121058993809853128792382425425507315758921975340564810424303160455069096558687026616771028629060280318800048984850429104924036193703515227460262324051154267318767728375732829596082819890956884172016068499243733410402170378286724312471419805200183238726658173781500929626384453831442841099333236763065428542599128063204447946777048377374390957947246087390567878387147899066382490069914521762754275957918350785590249135/35^(n-1)%35+n^(1007*(621^-1))/1+1

```

Verification program, Search program

# Answer
> 7 votes
# Score 194

```
1%(2^(n*30+16)%(n*30+17))*(1%(2^(n*30+22)%(n*30+23))*(1%(2^(n*30+28)%(n*30+29))*(1%(2^(n*30+12)%(n*30+13))*(1%(2^(n*30+6)%(n*30+7))*(1%(2^(n*30+10)%(n*30+11))*(1%(2^(n*30+18)%(n*30+19))*(-18)+8)+4)-6)-16)+6)+6)+n*30+17+702*0^(((n-360)*(n-523)*(n-654)*(n-941))^2)

```

Verification, generation code

This is golfing down the excellent solution of Max Kubierschky, who said they will no longer spend time updating their answer. See their answer for an explanation of the strategy. The formula here is largely the same, but was shortened by removing repetition and introducing cancellations.

**Branching**

The main improvement is the arithmetic formula used to branch on a condition:

```
if b1: t1
else: t2

```

Previously, this was done as `b1*t1+(1-b1)*t2`. This meant the condition `b1` needed to be repeated twice, which was costly because the condition of Fermat-primality used a relatively long formula.

We instead regroup `b1*t1+(1-b1)*t2` into `b1*(t1-t2)+t2`. Instead of repeating the condition `b1`, we repeat the output `t2`. So, we arrange to make \`t2 be short.

As used, one of the branches just gives a number (the successfully found prime), which the other branches into further conditions to continue the search.

```
if b1: t1
else:
 if b2: t2
 else:
  if b3: t3
  else: ...

```

Our method has the no-result `t2` repeated twice rather than `t1`, but we can fix this by negating the condition `b2` so that we can interchange `t1` and `t2`

We make it so that the twice-repeated `t1` is just a number, while the once-repeated `t2` is the long branch. We do this by negative the condition `b` to checking non-primality rather than primality. This is done by replacing the `1/stuff` check for `stuff==1` to instead be `1%stuff` for `stuff!=1` (in both cases, we know `stuff!=0`).

Doing this recursive expansion, we further find that it has terms like `t1-t2` that subtract two potential outputs. These can be simplified. Because each possible output has form `30*n+d`, we can cancel like `(30*n+17)-(30*n+23)==-6`, saving many instances of writing `30*n+`.

**Error fixing**

We use a variation of an idea suggested by Arnauld to fix the faulty cases in a shorter way, using 32 characters not counting parens.

```
+702*0^(((n-360)*(n-523)*(n-654)*(n-941))^2)

```

There are four non-prime outputs, and a brute-force search finds that adding `702` to each one makes them prime and distinct from all other outputs. We use an indicator function of being in those four cases, and adding `702` times that indicator. The indication function uses `0^` to check `==0` for a product of `n-k` for each failed input `k`. (If we can't rely on `0^0==1`, we can use `1/(1+_)` as a slightly longer alternative for \`\`0^\_\`.)

## Potential improvements

Other potential approaches might hide errors in a more efficient way by adaptively adjusting the numbers checked and the base of the pseudoprime, as suggested by in comments by Max Kubierschky.

---

## Score: 181

```
1%(4^(n*15+8)%(n*30+17))*(1%(4^(n*15+11)%(n*30+23))*(1%(4^(n*15+14)%(n*30+29))*(1%(4^(n*15+6)%(n*30+13))*(1%(8^(n*10+2)%(n*30+7))*(1%(4^(n*15+5)%(n*30+11))*(4-1%(4^(n*15+9)%(n*30+19))*9)+2)-3)-8)+3)+3)*2+n*30+17+702*0^(n%941%654%523%360)

```

Verification

This includes some hand-found optimizations. First, the faulty cases are checked in a shorter way found by Sisyphus, as `0^(n%941%654%523%360)`. This evaluates to `1` exactly for the exceptional inputs `n` of `360, 523, 654, 941` and zero otherwise. This mod chain works because each value happens to be less than double the previous one, including if we append `1000` to the end.

Other misc fixes uses that some values could be written shorter in base 10. Some of the expressions within the primality checks like `2^(n*30+16)` could be shortened like `4^(n*15+8)`. The various difference values were all even and could be written halved with a `*2` later. A `+stuff*(-18)` was changed to `-18*stuff`.

# Answer
> 5 votes
# Score ~~3627~~ 3611

<sup> -16 thanks to ovs </sup>

```
3+2*((673353961358307057272173964285854305022400426862712283607156657501677042657259951223221803215027383567602764647222388720899640048400919228204711994106584574819864931142671077276501015670240042908527525811814749482980228611256604904077801987663433451736668942035070032934698860829734874720469210161714878816011028172504741493933579809209910574296450420677024369299112300880495910602256708103075450576078270852444355116728596095883942463207003664230806032583002863238578022990852754983925220712751300313297384933847995017349232355819646993088732601141789442882215894245107446410040144336314519163731984860252867369601943162930927332772671777942282743699929467221065940282853778104585857297151693682829776011636408160070741255197392398379178628552688459418297270015040378809673826532754044991491047949801618973677882844224163396790251399862833397713210556181592058088280808086833457843140471319676974659849432132663508730287070561924395375776930976500890901210246692236611967263433823329001222292758613681022886491412907860270659758688163330174276013329990329027854152360352827518702283024606693537791396445418370900593234237528394888627532943238538996362251812152746408784587329522604812362612961371495908130917050336369858923800623610558102111936921275925428797115215197211803311011792800756612190446912977181671053858030216650244322510913097098308798280996846215666363104582951499187555401911800510241478422010155586326948174226637924523831893487438486345918123442987712606546163773523778000231233612013623430096825956978942500937017215764165647469497368906623052990700252559013399879211291330909786175176769030687149835775829911173638805247625058275472816919156779291864013317155789882424054286324759552057921576616305056718594449895582860551963359519586408623708864584561224246719261364576172798288646507616917260121960060868716498458065082069151627356119717481764663140004551411443836333454961570935788652411333156384108866105400945838983456882978708424835088504807894682236883745784973974040648206299840824904279658635709233240664508551436734587146655032803436637243796714343511860088974399527943200654250140528821734417790449393945285632254377776046148129706540302453728840180914936819379438129581929627122804300127402709137830767613859849789109693350209773812357814726116008525681439255652001075856620439770299106395170302718499156517954285958747428744867003478259930463719139124320607133501439062288308905310881240867020273433661589445461066595657102669091317184108354554780017050349715850637537754106644755877075976187792445454821491839099929811225904639357052860836725499598183388404838427261429247485564633277253719915506486176500112852688184110139443587654583288837334797167835735314125201482147157537170750071301166473892100288867902409680472473344928486818014572141062729317739432887663007563551474290116952695377398184560337726343710669752174924005456400102600864172580302332762119194992885413026313261935677976382585514252800149731204021813826627080668911910552674815596682803932260276187920122242385797617877679445263885318204673888387270960551456287016730721644217841772314017713996319546205478449021962852317888766140480391183821928016315770425629570172282014425326824523667359350036132550758310731296339346026078740156028410312853179295874487323332796505227759163992369277010277291451843685489537975456773437258824811891298037075841518405314798557707912615382278504559764233167102285790740913352590724521945879074542935442272119863497621828348597890290006456761410388942801963190048896271350965485295433493478609534842891151210843278069634083290205578635819949175811191179//(3963**(n-1)))%3963)

```

(Brackets added for clarity, but not counted in score).

This unpacks primes from a large number. There are 13 bits in the largest prime, but we can omit the last bit if we ignore the prime 2, since then the last bit is always 1.

You can also check the verification program.

I do not consider this anywhere close to optimal, but it's a good starting point.

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


title: Decide a C integer literal

text:
# Question
Title: Decide a C integer literal
# Objective

Given an ASCII string, decide whether it is a valid C integer literal.

# C integer literal

A C integer literal consists of:

* One of:

+ `0` followed by **zero or more** octal digits (`0``7`)
    + A nonzero decimal digit followed by **zero or more** decimal digits (`0``9`)
    + `0X` or `0x`, followed by **one or more** hexadecimal digits (`0``9`, `A``F`, and `a``f`)
* optionally followed by one of:

+ One of `U` or `u`, which are the "unsigned" suffixes
    + One of `L`, `l`, `LL`, or `ll`, which are the "long" and "long long" suffixes
    + Any combination of the above, in any order.

Note that there can be arbitrarily many digits, even though C doesn't support arbitrary-length integers. Likewise, even if the literal with `l` and co would overflow the `long` type or co, it is still considered a valid literal.

Also note that there must **not** be a leading plus or minus sign, for it is not considered to be a part of the literal.

# Rules

* It is implementation-defined to accept leading or trailing whitespaces.
* Non-ASCII string falls in *don't care* situation.

# Examples

## Truthy

* `0`
* `007`
* `42u`
* `42lu`
* `42UL`
* `19827489765981697847893769837689346573uLL` (Digits can be arbitrarily many even if it wouldn't fit the `unsigned long long` type)
* `0x8f6aa032838467beee3939428l` (So can to the `long` type)
* `0XCa0` (You can mix cases)

## Falsy

* `08` (Non-octal digit)
* `0x` (A digit must follow `X` or `x`)
* `-42` (Leading signature isn't a part of the literal)
* `42Ll` (Only `LL` or `ll` is valid for the `long long` type)
* `42LLLL` (Redundant type specifier)
* `42Uu` (Redundant type specifier)
* `42Ulu` (Redundant type specifier)
* `42lul` (Redundant type specifier)
* `42H` (Invalid type specifier)
* `0b1110010000100100001` (Valid C++, but not valid C)
* `Hello`
* Empty string

# Ungolfed solution

## Haskell

Doesn't recognize leading or trailing whitespaces.

Returns `()` on success. Monadic failure otherwise.

```
import Text.ParserCombinators.ReadP

decideCIntegerLit :: ReadP ()
decideCIntegerLit = do
    choice [
        do
            '0' <- get
            munch (flip elem "01234567"),
        do
            satisfy (flip elem "123456789")
            munch (flip elem "0123456789"),
        do
            '0' <- get
            satisfy (flip elem "Xx")
            munch1 (flip elem "0123456789ABCDEFabcdef")
        ]
    let unsigned = satisfy (flip elem "Uu")
    let long = string "l" +++ string "L" +++ string "ll" +++ string "LL"
    (unsigned >> long >> return ()) +++ (optional long >> optional unsigned)
    eof

```

# Answer
# Retina 0.8.2, ~~60~~ 59 bytes

```
i`^(0[0-7]*|0x[\da-f]+|[1-9]\d*)(u)?(l)?(?-i:\3?)(?(2)|u?)$

```

Try it online! Link includes test cases. Edit: Saved 1 byte thanks to @FryAmTheEggMan. Explanation:

```
i`

```

Match case-insensitively.

```
^(0[0-7]*|0x[\da-f]+|[1-9]\d*)

```

Start with either octal, hex or decimal.

```
(u)?

```

Optional unsigned specifier.

```
(l)?

```

Optional length specifier.

```
(?-i:\3?)

```

Optionally repeat the length specifier case sensitively.

```
(?(2)|u?)$

```

If no unsigned specifier yet, then another chance for an optional specifier, before the end of the literal.
> 9 votes

# Answer
# Perl 5 `-p`, ~~65~~ 61 bytes

*@NahuelFouilleul shaved 4 bytes*

```
$_=/^(0[0-7]*|0x\p{Hex}+|[1-9]\d*)(u?l?l?|l?l?u?)$/i*!/lL|Ll/

```

Try it online!
> 5 votes

# Answer
# Java 8 / Scala polyglot, ~~89~~ 79 bytes

```
s->s.matches("(?!.*(Ll|lL))(?i)(0[0-7]*|[1-9]\\d*|0x[\\da-f]+)(u?l?l?|l?l?u?)")

```

-10 bytes thanks to *@NahuelFouilleul*

Try it online in Java 8.
Try it online in Scala (except with `=>` instead of `->` \- thanks to *@TomerShetah*).

**Explanation:**

```
s->           // Method with String parameter and boolean return-type
  s.matches(  //  Check whether the input-string matches the regex
    "(?!.*(Ll|lL))(?i)(0[0-7]*|[1-9]\\d*|0x[\\da-f]+)(u?l?l?|l?l?u?)")

```

*Regex explanation:*

In Java, the `String#matches` method implicitly adds a leading and trailing `^...$` to match the entire string, so the regex is:

```
^(?!.*(Ll|lL))(?i)(0[0-7]*|[1-9]\d*|0x[\da-f]+)(u?l?l?|l?l?u?)$

```

```
 (?!         )     # The string should NOT match:
^   .*             #   Any amount of leading characters
      (     )      #   Followed by:
       Ll          #    "Ll"
         |lL       #    Or "lL"
                   # (Since the `?!` is a negative lookahead, it acts loose from the
                   #  rest of the regex below)

 (?i)              # Using case-insensitivity,
^    (             # the string should start with:
       0           #   A 0
        [0-7]*     #   Followed by zero or more digits in the range [0,7]
      |            #  OR:
       [1-9]       #   A digit in the range [1,9]
            \d*    #   Followed by zero or more digits
      |            #  OR:
       0x          #   A "0x"
         [     ]+  #   Followed by one or more of:
          \d       #    Digits
            a-f    #    Or letters in the range ['a','f']
     )(            # And with nothing in between,
              )$   # the string should end with:
        u?         #   An optional "u"
          l?l?     #   Followed by no, one, or two "l"
       |           #  OR:
        l?l?       #   No, one, or two "l"
            u?     #   Followed by an optional "u"

```
> 5 votes

# Answer
# C# (.NET Core), 197 191 bytes

@nwellnhof shaved 6bytes:

```
using c=System.Console;class P{static void Main(){c.WriteLine(System.Text.RegularExpressions.Regex.IsMatch(c.ReadLine(),@"^(?!.*(Ll|lL))(?i)(0[0-7]*|[1-9]\d*|0x[\da-f]+)(u?l?l?|l?l?u?)$"));}}

```

Original:

```
using c=System.Console;using System.Text.RegularExpressions;class P{static void Main(){c.WriteLine(Regex.IsMatch(c.ReadLine(),@"^(?!.*(Ll|lL))(?i)(0[0-7]*|[1-9]\d*|0x[\da-f]+)(u?l?l?|l?l?u?)$"));}}

```

Try it online!
> 5 votes

# Answer
# Python 3, 103 bytes

```
import re;re.compile("^(0[0-7]*|[1-9]\d*|0[xX][\dA-Fa-f]+)([uU](L|l|LL|ll)?|(L|l|LL|ll)[uU]?)?$").match

```

Try it online!

just a basic regex, probably very suboptimal

returns a match object for truthy and None for falsy; input may not contain surrounding whitespace

-3 bytes thanks to Digital Trauma (on my Retina answer)
-1 byte thanks to FryAmTheEggman (on my Retina answer)
-3 bytes thanks to pxeger
> 4 votes

# Answer
# Retina 0.8.2, 73 bytes

```
^(0[0-7]*|[1-9]\d*|0[xX][\dA-Fa-f]+)([uU](L|l|LL|ll)?|(L|l|LL|ll)[uU]?)?$

```

Try it online!

Just the same regex I used. First time using Retina, I'm sure this can be optimized with some Retina golf things!

-3 bytes thanks to Digital Trauma
-1 byte thanks to FryAmTheEggman
> 3 votes

# Answer
# JavaScript (ES6),  ~~77~~  76 bytes

*Saved 1 byte thanks to @l4m2*

```
s=>/^(0x[\da-f]+|0[0-7]*|[1-9]\d*)(u?l?l?|l?l?u?)$/i.test(s)>/Ll|lL/.test(s)

```

Try it online!

### How?

The first regex is case-insensitive. The only invalid patterns that cannot be filtered out that way are `"Ll"` and `"lL"`. So we use a 2nd case-sensitive regex to take care of them.
> 2 votes

# Answer
# 05AB1E, ~~63~~ ~~61~~ 62 bytes

```
„Uuõª„LLæDl«âDí«JéRʒÅ¿}нõ.;Ðć_ilDć'xQiA6£мÐþQë\7ÝKõQë\þQ}sõÊ*

```

This isn't too easy without regexes.. :/ Can definitely be golfed a bit more, though.

+1 byte as bug-fix for inputs like `"u"`, `"l"`, `"LL"`, etc. (thanks for noticing *@Neil*)

Try it online or verify all test cases.

**Explanation:**

```
„Uu                 # Push string "Uu"
   õª               # Convert it to a list of characters, and append an empty string:
                    #  ["U","u",""]
     „LL            # Push string "LL"
        æ           # Take its powerset: ["","L","L","LL"]
         Dl         # Create a lowercase copy: ["","l","l","ll"]
           «        # Merge the lists together: ["","L","L","LL","","l","l","ll"]
            â       # Create all possible pairs of these two lists
             Dí     # Create a copy with each pair reversed
               «    # Merge the list of pairs together
                J   # Join each pair together to a single string
                 éR # Sort it by length in descending order

```

We now have the list:

```
["llu","LLu","llU","LLU","ull","uLL","Ull","ULL","ll","LL","lu","lu","Lu","Lu","lU","lU","LU","LU","ll","LL","ul","ul","uL","uL","Ul","Ul","UL","UL","l","l","L","L","u","u","U","U","l","l","L","L","u","u","U","U","","","",""]

```

```
ʒ                   # Filter this list by:
 Å¿                 #  Where the (implicit) input ends with this string
}н                  # After the filter: only leave the first (longest) one
  õ.;               # And remove the first occurrence of this in the (implicit) input
ÐD                  # Triplicate + duplicate (so there are 4 copies on the stack now)
  ć                 # Extract head; pop and push remainder-string and first character
                    # separated to the stack
   _i               # If this first character is a 0:
     l              #  Convert the remainder-string to lowercase
      D             #  Duplicate it †¹
       ć            #  Extract head again
        'xQi       '#  If it's equal to "x":
            A       #   Push the lowercase alphabet
             6£     #   Only leave the first 6 characters: "abcdef"
               м    #   Remove all those characters from the string
                Ð   #   Triplicate it †²
                 þ  #   Only keep all digits in the copy
                  Q #   And check that the two are still the same
                    #   (thus it's a non-negative integer without decimal .0s)
          ë         #  Else:
           \        #   Discard the remainder-string
            7Ý      #   Push list [0,1,2,3,4,5,6,7]
              K     #   Remove all those digits
               õQ   #   Check what remains is an empty string
   ë                # Else:
    \               #  Discard the remainder-string
     þ              #  Only keep all digits
      Q             #  And check that the two are still the same
                    #  (thus it's a non-negative integer without decimal .0s)
   }s               # After the if-else: Swap the two values on the stack
                    # (this will get the remaining copy of †² for "0x" cases,
                    #  or the remaining copy of †¹ for other cases)
     õÊ             # Check that this is NOT an empty string
       *            # And check that both are truthy
                    # (after which the result is output implicitly)

```
> 2 votes

# Answer
# AWK, 86 bytes

```
{print/^(0[0-7]*|[1-9][0-9]*|0[xX][0-9A-Fa-f]+)([uU](L|l|LL|ll)?|(L|l|LL|ll)[uU]?)?$/}

```

Try it online!

Simply prints truthy or falsey depending on whether or not the input line matches the regex. Doesn't accept leading or trailing whitespaces.
> 2 votes

# Answer
# Charcoal, 76 bytes

```
≔⊟Φ³¬⌕↧θ…0xιη≔✂↧θη⁻ＬθＬ⊟Φ⪪”{“↧←；⭆δa”¶⁼ι↧…⮌θＬι¹ζ›∧⁺Ｌζ¬⊖η⬤ζ№Ｅ∨×⁸ηχ⍘λφι∨№θLl№θlL

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⊟Φ³¬⌕↧θ…0xιη

```

Find the length of the longest prefix of `0x` in the lowercased input.

```
≔✂↧θη⁻ＬθＬ⊟Φ⪪”{“↧←；⭆δa”¶⁼ι↧…⮌θＬι¹ζ

```

Slice off the prefix and also check for a lowercase suffix of `ull`, `ul`, `llu` or `lu`, and if so then slice that off as well.

```
›...∨№θLl№θlL

```

The original input must not contain `Ll` or `lL`.

```
∧⁺Ｌζ¬⊖η

```

The sliced string must not be empty unless the prefix was `0`.

```
⬤ζ№Ｅ∨×⁸ηχ⍘λφι

```

Convert the prefix length to `10`, `8` or `16` appropriately, then take that many base 62 digits and check that all of the remaining lowercased characters are one of those digits.
> 2 votes

# Answer
# Elixir, 74 bytes

```
&(&1=~~r/^(0[0-7]*|[1-9]\d*|0x[\da-f]+)(u?l?l?|l?l?u?)?$/i&&!(&1=~~r/Ll/))

```

Try it online!
> 2 votes

# Answer
# Haskell, 169 bytes

```
import Data.Char
s!p=s>""&&dropWhile p s`elem`do u<-["","u","U"];l<-"":words"L l LL ll";[u++l,l++u]
f('0':x:s)|elem x"xX"=s!isHexDigit|1<2=(x:s)!isOctDigit
f s=s!isDigit

```

Try it online!
> 1 votes

---
Tags: code-golf, string, decision-problem, c
---


title: Sum my Fibonaccified divisors!

text:
# Question
Title: Sum my Fibonaccified divisors!
The famous Fibonacci sequence is `F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1)` (for this challenge we are beginning with 0).

Your challenge: Given *n*, output the sum of all the *d*th Fibonacci numbers for all divisors *d* of the *n*th Fibonacci number. If you prefer more formal notation,

**Input**: a positive integer *n*

**Output**: the sum

For example, consider `n=4`. `F(4) = 3`The divisors of 3 are 1 and 3, so the output should be `F(1) + F(3) = 1 + 2 = 3`.

For `n=6`, `F(6) = 8`, and the divisors of 8 are 1, 2, 4, 8, so the output is `F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26`.

Test Cases:

```
1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26

```

This is , shortest answer in bytes wins. Standard loopholes apply.

# Answer
# Actually, 5 bytes

```
F÷♂FΣ

```

Try it online!

### How it works

```
       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.

```
> 2 votes

# Answer
# Jelly, 7 bytes

```
ÆḞÆDÆḞS

```

Try it online!

Explanation:

```
ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum

```
> 6 votes

# Answer
## Mathematica, 29 bytes

```
f=Fibonacci;f@#~DivisorSum~f&

```
> 4 votes

# Answer
# Mathematica Simplified, 14 bytes

```
Fi@#~Div9`~Fi&

```

Oh well, this ended up being identical to @MartinEnder's solution...
> 4 votes

# Answer
# Japt, 11 bytes

```
MgU â x@MgX

```

Try it online!
> 3 votes

# Answer
## Alice, ~~38~~ 36 bytes

*Thanks to Leo for saving 2 bytes.*

```
/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

```

Try it online!

Almost certainly not optimal. The control flow is fairly elaborate and while I'm quite happy with how many bytes that saved over previous versions, I have a feeling that I'm overcomplicating things that there might be a simpler *and* shorter solution.

### Explanation

First, I need to elaborate a bit on Alice's return address stack (RAS). Like many other fungeoids, Alice has a command to jump around in the code. However, it also has commands to return to where you came from, which lets you implement subroutines quite conveniently. Of course, this being a 2D language, subroutines really only exist by convention. There's nothing stopping you from entering or leaving a subroutine through other means than a return command (or at any point in the subroutine), and depending on how you use the RAS, there might not be a clean jump/return hierarchy anyway.

In general, this is implemented by having the jump command `j` push the current IP address to the RAS before jumping. The return command `k` then pops an address of the RAS and jumps there. If the RAS is empty, `k` does nothing at all.

There are also other ways to manipulate the RAS. Two of these are relevant for this program:

* `w` pushes the current IP address to the RAS *without* jumping anywhere. If you repeat this command you can write simple loops quite conveniently as `&w...k`, which I've already done in past answers.
* `J` is like `j` but *doesn't* remember the current IP address on the RAS.

It's also important to note that the RAS stores no information about the *direction* of the IP. So returning to an address with `k` will always preserve the *current* IP direction (and therefore also whether we're in Cardinal or Ordinal mode) regardless of how we passed through the `j` or `w` that pushed the IP address in the first place.

With that out the way, let's start by looking into the subroutine in the above program:

```
01dt,t&w.2,+k

```

This subroutine pulls the bottom element of the stack, **n**, to the top and then computes the Fibonacci numbers **F(n)** and **F(n+1)** (leaving them on top of the stack). We never need **F(n+1)**, but it will be discarded outside the subroutine, due to how `&w...k` loops interact with the RAS (which sort of requires these loops to be at the *end* of a subroutine). The reason we're taking elements from the bottom instead of the top is that this lets us treat the stack more like a queue, which means we can compute all the Fibonacci numbers in one go without having to store them elsewhere.

Here is how this subroutine works:

```
                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

```

The end of the loop is a bit tricky. As long as there's a copy of the 'w' address on the stack, this starts the next iteration. Once those are depleted, the result depends on how the subroutine was invoked. If the subroutine was called with 'j', the last 'k' returns there, so the loop end doubles as the subroutine's return. If the subroutine was called with 'J', and there's still an address from earlier on the stack, we jump there. This means if the subroutine was called in an outer loop itself, this 'k' returns to the beginning of that *outer* loop. If the subroutine was called with 'J' but the RAS is empty now, then this 'k' does nothing and the IP simply keeps moving after the loop. We'll use all three of these cases in the program.

Finally, on to the program itself.

```
/o....
\i@...

```

These are just two quick excursions into Ordinal mode to read and print decimal integers.

After the `i`, there's a `w` which remembers the current position before passing into the subroutine, due to the second `/`. This first invocation of the subroutine computes `F(n)` and `F(n+1)` on the input `n`. Afterwards we jump back here, but we're moving east now, so the remainder of the program operators in Cardinal mode. The main program looks like this:

```
;B1dt&w;31J;d&+
        ^^^

```

Here, `31J` is another call to the subroutine and therefore computes a Fibonacci number.

```
                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)]
      we're treating the stack as a queue,
      the last iteration will process the
      first divisor for a second time.
      Luckily, the first divisor is always
      1 and F(1) = 1, so it doesn't matter
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.

```
> 3 votes

# Answer
# 05AB1E, 11 bytes

```
!ÅFDI<èÑ<èO

```

Try it online!

**Explanation**

```
!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum

```
> 2 votes

# Answer
## Haskell, 54 bytes

```
f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

```

Usage example: `g 6` -\> `26`. Try it online!
> 2 votes

# Answer
# R, 77 bytes

```
F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

```

Makes use of the 'gmp' library. This has a builtin Fibonacci function and provides the ability to do large numbers. It caused a few issues with seqs and applys, though it is still smaller than creating my own Fibonacci function.

**Explanation**

```
F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

```

**Test**

```
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2:
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2:
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2:
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

```

**Without using gmp**

**81 bytes**, Recursive function that is hopelessly slow when large (9+) numbers are picked

```
F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

```

**88 bytes**, Binet's formula that will work reasonably well with larger numbers, but still hits integer limit quite quickly

```
F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))

```
> 2 votes

# Answer
# Axiom, 68 bytes

```
g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

```

some test

```
(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger

```
> 1 votes

# Answer
# Pari/GP, 34 bytes

```
n->sumdiv((f=fibonacci)(n),x,f(x))

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~89~~ 84 bytes

<sup>-5 bytes thanks to ovs</sup>

```
lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

```

Try it online!
> 1 votes

# Answer
# Perl 6, 49 bytes

```
{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}

```
> 0 votes

# Answer
# C (gcc), ~~93~~ ~~90~~ 80 bytes

```
F(n){n=n<2?n:F(n-1)+F(n-2);}i,s;f(n){for(s=0,i=F(n);i;i--)s+=F(n)%i?0:F(i);n=s;}

```

Try it online!
> 0 votes

# Answer
# JavaScript (ES6), ~~105~~ ~~104~~ ~~103~~ ~~101~~ 97 bytes

```
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

```

---

## Try it

```
f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)
```

```
<input id=j type=number><pre id=o>
```
> 0 votes

# Answer
# CJam, 26 bytes

```
qi_[XY@{_2$+}*]_@\f%:!.*:+

```

Try it online!

I'm sure it can be done better. Explanation:

The idea is to have an array of Fibonacci numbers and dot product it with an array with 1s and 0s if that number is or is not a divisor of the input.

```
qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise)
                      .*:+         Dot product those two arrays

```
> 0 votes

# Answer
## JavaScript (ES6), ~~76~~ 65 bytes

```
f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

```

### Test cases

```
f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))
```
> 0 votes

# Answer
## Q, 75 bytes

```
{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}

```
> 0 votes

# Answer
# Add++, 89 bytes

```
D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}
D,d,@,{g}dF€gs

```

Try it online!
> 0 votes

# Answer
# Husk, 8 bytes

```
ṁ!İfḊ!İf

```

Try it online!
> 0 votes

---
Tags: code-golf, number-theory, fibonacci, division
---


title: Coffee Machine Machine

text:
# Question
Title: Coffee Machine Machine
You left your computer for too long, and it went to sleep. Wake it up again by printing the following coffee maker.

```
________._________
|      | \   -   /
|  ||  |  \  -  /
|  ||  |___\___/
|  ||  |     X
|      |    ___
|      |   / - \
|______|  /  -  \
| ____ | /_______\
||7:30||__________
||____|           |
|_________________|

```

Reference image I used.

# Specs

* Any input must be included in the byte total.
* Leading newlines and trailing whitespace is allowed.
* Shortest code in bytes wins.

# Answer
> 8 votes
# SOGL V0.12, 78 bytes

```
≈p⁽.*%θ|»Y?v▼mB8█[=ρļiρKτ¾Γb    2⁴⅟┼¤Μ╬(׀⁾⌠○Yyλ{╝<-³|k¤↑E*UH∙æ¹ΘNσx↔§÷πm‛⁾ņμ׀⁴@≤‘

```

Try it Here!

SOGL compression beats bubblegum!

# Answer
> 20 votes
# CoffeeScript, 219 bytes

*Thanks to @totallyhuman for saving 4 bytes!*

```
->"""#{l="________"}.#{l}_
#{s="|      |"} \\   -   /
#{t="|  ||  |"}  \\  -  /
#{t}___\\___/
#{t}     X
#{s}    ___
#{s}   / - \\
|______|  /  -  \\
| ____ | /_______\\
||7:30||#{l}__
||____|           |
|#{l}#{l}_|"""

```

Try it online!

# Answer
> 6 votes
# Befunge, ~~166~~ 162 bytes

```
55+31p"kvvvvvvvvgf:::::kvugvvvvvj6,jHvvvs>?vqg[@:P>vvvg[|P:f::>Jv"v
:0  /\|_-37X.v"vvvv{vvvvg:::>=:@:G>f>f:=|:G>f>fv`vUg:j:>::N>::f::"<
g1+2%+56:-*49<_@#:,g1/+56,

```

Try it online!

**Explanation**

This is using a fairly simple compression scheme where every two characters are encoded into a pair as a base 11 number.

We start by translating the characters into indices in a lookup table to minimise their size - this gives us one index in the range 0 to 11, and a second in the range 0 to 8. These indices are combined into a single number as `n = i1 + i2*11`. We then add a additional offset to translate that number into the range of printable ASCII characters, so it can be stored in a Befunge string.

When decoding we just perform this process in reverse. We subtract the offset, split the value into two parts with `i1 = n%11` and `i2 = n/11`, and then lookup those indices in the translation table to obtain the final characters to output.

**Bonus Coffee Mug**

```
55+37p"kvvvvvvvvgf::"v
v",6jvvvvvguvk:::"   <
>"jHvvvs>?vqg[@:P"   v
v"vJ>::f:P|[gvvv>"   <
>"::f::>N::>:j:gU"   v
v"f>f:=|:G>f>fv`v"   <
>">G:@:=>:::gvvvv"   v
:0 X/\|_-37X.v"vvvv{"<
 @v2%+56:-*49<<_>
  >+7g,65+/7g,:^

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES6), 176 bytes

```
_=>`22__.222511| 31-1/4636-6/4232/416X511| 12511|1/ - 3522|6/6-635 2_ | /2_235|7:0||222_5|2_|6111|522222__|`.replace(/\d/g,s=>[30,'   ','___','\\',`
|  ||  |`,`
|`,'  '][s]||s)

```

Try it online!

# RegPack'd version, ~~186~~ 184 bytes

```
_=>[...'CaFfEiNe!'].reduce((s,c)=>(x=s.split(c)).join(x.pop()),`!E_.C!
f| \\a-aiN\\e-ei|!\\!iNaX
fNe!
fN / - FCN/e-eF E | /!EF|7:30||CE
||Efea|
|CCE_|E__a N|ei/
N|NE!_fNeeF\\
|ae C!!`)

```

Try it online!

# Answer
> 3 votes
# Bubblegum, 83 bytes

```
00000000: 4d8c d501 0230 1403 ff3b 4507 c01d 16c1  M....0...;E.....
00000010: c922 199e abf7 9eab 2a2b 3582 63c6 f183  ."......*+5.c...
00000020: 5f62 eb60 4a0c a5b7 9c3b 923e d8bc 028f  _b.`J....;.>....
00000030: f104 e6a7 d89a 0f9f 6065 4c9d 5fd2 8902  ........`eL._...
00000040: 56d6 2ad0 f2f9 b6df d8ea d0aa 671d d75f  V.*.........g.._
00000050: 33fe 03                                  3..

```

Try it online!

# Answer
> 3 votes
# C# (.NET Core), 189 bytes

```
()=>@"uu__.uuu
|ss| \s-s/
|  ||  |  \  -  /
|  ||  |u\u/
|  ||  |s  X
|ss| su
|ss|s/ - \
|uu|  /  -  \
| u_ | /u_u\
||7:30||uuu_
||u_|  sss|
|uuuuu__|".Replace("u","___").Replace("s","   ")

```

Try it online!

---

The lazy solution:

# C# (.NET Core), 223 bytes

```
()=>@"________._________
|      | \   -   /
|  ||  |  \  -  /
|  ||  |___\___/
|  ||  |     X
|      |    ___
|      |   / - \
|______|  /  -  \
| ____ | /_______\
||7:30||__________
||____|           |
|_________________|"

```

Try it online!

# Answer
> 3 votes
# Bash, 169 165 bytes

Thanks to Nahuel Fouilleul for saving 4 bytes!

```
base64 -d<<<H4sIAECtIFoCA1WOUQqAMAxD/3uKXmBO8EPwJH4MepEc3sRVrQ86WJZkjZgs8WDwG/jg2ThdEjQurVWFgcGpFnJ+JeRXyjAbhmH+Bt1VSUXGoKXnJpSwH9sKRNkOGXuBlfcEdgGenVY82QAAAA==|zcat

```

Try it online!

`gzip` seems to compress it a lot better than `bzip2` and `xz`.

# Answer
> 1 votes
# Python 2, ~~282~~ 265 bytes

```
a,b,c,d,e,u='_ . | \ / ||'.split();s=' ';t=s*2;z=c+t;y=c+s*6;v=z+u+t
for x in a*8+b+a*9,y+c+s+d+s*3+a+s*3+e,v+z+d+t+a+t+e,v+c+a*3+d+a*3+e,v+c+s*5+"X",y+c+s*4+a*3,y+c+s*3+e+s+a+s+d,y+z+e+t+a+t+d,c+s+a*4+s+c+s+e+a*7+d,u+"7:30"+c*2+a*10,u+a*4+c+s*11+c,c+a*17+c:print x

```

Try it online!

Actually a fair bit longer than just

```
print'''TheCoffeePot'''

```

which would be 227 but it works so posting it anyway as it's the shortest (and so far only) Python answer :)

# Answer
> 1 votes
# brainfuck, 689 bytes

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

```

Try it online!

First I generate a table of 13 characters that are used. To save bytes, I first generate their closest character codes that are divisible by 10. Then I add 0-9 to each of them. Finally I just print them in particular orders.

Unminified source:

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

```

# Answer
> 1 votes
# , 174 164 bytes

Some silly RLE-like compression, lengths encoded as base 99 number :)

```
_19]\(10#.inv 99x#._28+a.i.'Ls}DR#Er-B{SBh(+dXQwBE=]|LrC$v:x5u}sa"z>f=#Y*?Tzzo8PmK7rZay')#,'_._||\-/|||\-/|||_\_/|||x||_||/-\|_|/-\|_|/_\|7:30|__|_| ||__|',.' '

```

Try it online!

# Answer
> 1 votes
# brainfuck, 546 bytes

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

```

Try it online!

# Answer
> 0 votes
# Python 3, ~~220~~ ~~216~~ 213 bytes

```
b=0;c='\n -./037:X\\_|'
for i in r"*Z_7stu{NzKBNJ,IOOe-0qj9?s7C?r/XYUX_Fs\hM-\NY+VJ+A.E]?vAx&=gUVSBRq4>PB+]OtO3%PWn%^0c0'B]d5P-$X,(7U$nVq02NRjMp'AAvl!Da(zyVyI":b=b*92+ord(i)-32
while b:print(c[b%13],end='');b//=13

```

Try it online!

Code to generate code

# Answer
> 0 votes
# Cubically, ~~652~~ 626 bytes

```
⇒@@@@@@@@
RU+532f1-411@+411f1@-3320@+5432@-4422@@@@@@+4422@-4422@+220@-220@@@+4-0@-4+0@@@+1@-4000@+5432@-4422@@+4422@@-4422@@+4422@-4422@@+220@-220@@+4-0@-4+0@@+1@-4000@+5432@-4422@@+4422@@-4422@@+4422@-50+4@@@-1+00@+1-00@@@-50@-4000@+5432@-4422@@+4422@@-4422@@+4422@-4422@@@@@+311@-333@+5432@-4422@@@@@@+4422@-4422@@@@+510@@@-3320@+5432@-4422@@@@@@+4422@-4422@@@+1@-1@+4-0@-4+0@+220@-3311@+5432@-50+4@@@@@@+50-4@-4422@@+1@-1@@+4-0@-4+0@@+220@-3311@+5432@-4422@+510@@@@-510@+4422@-4422@+1@+50@@@@@@@-1+00@-3311@+5432@@-52@+1-00@-3+4@-1+00@+541@@-50+4f1@@-3320@+5432@@-50+4@@@@+50-4@-4422f1@@@+4422@-5432@+5432@-50+4f1f1@+50-4@

```

Found via this tool and golfed via search-and-replace, plus a couple custom optimizations.

Try it online!

# Answer
> 0 votes
# Bash, 108 bytes

`zcat`

Input is a 104 byte sequence on stdin (represented in hexadecimal below) of the coffee pot compressed in gzip format:

```
1F 8B 08 01 0F 2D 32 5A 02 00 5D 8C 41 0A 80 30
0C 04 EF 7D 45 3E A0 15 3C 08 BE C4 43 20 1F D9
C7 3B B1 96 56 87 A6 90 21 BB F1 B2 46 A7 C8 1E
64 CE BF 30 35 95 18 9E A3 66 43 C0 99 F9 04 AE
51 02 9F 52 C2 34 78 11 16 94 3B 22 8D 05 70 52
A3 81 D2 71 EE 9B B8 ED A0 5A 6C 20 BA FE A8 DC
9E 9D 56 3C D9 00 00 00

```

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---