# Question
Title: Extend the most recent "nice" OEIS sequence: stepping stone puzzle on a grid
Today Neil Sloane of the OEIS sent out an email asking for a confirmation of the current terms, and computation of some larger terms of the latest OEIS sequence A337663 with the keyword "nice".

Here's how this sequence works: You label \\$n\\$ cells on the infinite square grid with \\$1\\$s, and then

> place the numbers \\$2,3,4,\dots,m\\$ in order, subject to the rule that when you place \\$k\\$, the sum of its \[horizontal, vertical, and diagonal\] neighbors must equal \\$k\\$. Then \\$A337663(n)\\$ is the maximum \\$m\\$ that can be achieved over all initial placings of the \\$1\\$-cells.

Here's an illustration of \\$A337663(2) = 16\\$:

```
+----+----+----+----+----+----+
|  9 |  5 | 10 | 11 |    |    |
+----+----+----+----+----+----+
|    |  4 |  1 |    |    |    |
+----+----+----+----+----+----+
| 12 |  8 |  3 |  2 |    | 16 |
+----+----+----+----+----+----+
|    |    |    |  6 |  1 | 15 |
+----+----+----+----+----+----+
|    |    | 13 |  7 | 14 |    |
+----+----+----+----+----+----+

```

Notice that the \\$2\\$-cell has two \\$1\\$-cells as neighbors (and \\$1 + 1 = 2\\$); the \\$3\\$-cell has a \\$1\\$-cell and a \\$2\\$-cell as neighbors (and \\$1 + 2 = 3\\$); etc.

# The challenge.

Like this previous challenge, the goal of this is to compute as many terms as possible in this sequence, which begins `1, 16, 28, 38` and where the \\$n\\$-th term is \\$A337663(n)\\$.

Run your code for as long as you'd like. The winner of this challenge will be the user who posts the most terms of the sequence, along with their code to generate it. If two users post the same number of terms, then whoever posts their last term earliest wins.

# Answer
# C + OpenMP, N=5

*New version with a proper handling of the 112-1113 case.*

```
a(5) = 49
 0 46 26  0  0  0  0  0  0  0  0 35  0

 0 20  0  6 28 48  0  0  0  0 34  1 36

39 19  1  2  3 17  0 30  0  0 33  0 37

 0  0 18  7  1  4  9  0 21 32  0  0  0

 0 40  0  8 38  5 43 10 11  0 44  0  0

 0  0 22  0 13  0 15  0  1 12  0  0  0

47 23  0 14 27  0 31 16 29  0  0  0  0

 0 24  1  0 41  0  0  0 45  0  0  0  0

49 25  0 42  0  0  0  0  0  0  0  0  0

```

### How it works

The program will only work for N=5, for higher numbers you'd need some adjustments. First lets take a look how an easier approach for N=4 would look like. We need at least 112 next to each other in some arrangement. Because there are only two 1s left, every other number cannot be made only by new 1s.

So starting from the six possible starting positions for 112:

```
1 1   1 2 1   1 _ 1   1 _   1 _ _   1 _ _
2 _           _ 2 _   2 1   _ 2 1   _ 2 _
                                    _ _ 1

```

we can take a look at every space placed two spots away and check their sum (Note: with some proper case handling, you should be fine to check the direct neighbors, though I took the safe route).

```
      0 0 0 0 0 0
      0 1 2 2 1 0

```

1 1 -\> 0 3 . . 1 0 2 _ 0 3 . 4 1 0 0 2 2 2 0 0 0 0 0 0 0 0

For every spot: check if the sum is the next needed number (in this case 3) or if we can still place some 1s: is the sum plus some newly added 1s the next needed number. In the latter case, we need to make sure that the new 1s don't interfere with existing numbers \> 1, e.g.

```
3 1
1 1 1
  2

```

wouldn't be valid as the 2-placement would have been illegal, but

```
1 1
2   3 1
    1

```

would be fine. Note that I only increase the bounding box for two spots around non-1 numbers. So for the lower right corner, the next spots to try are as following:

```
1 _ _ _
_ 3 1 _
_ 1 _ _
_ _ _ _
  x

```

The `x` spot wouldn't get checked, as its number would only neighbor new 1s – and for N=4 this is not possible as mentioned before.

For N\>4 this get a little more complicated: it is not guaranteed that every number will be connected to the first 112. Another cluster might start independently: 1113. But after that every number cannot be made only of new 1s, thus will be connected to either 1113 or 112. Note that we don't have to handle anything else in the N=5 case (but would need for N\>5): having two clusters with 1 and 11114 will already be handled, as 2 and 3 must also be placed in 11114; so every 11114 will already be checked by 112 or 1113.

So we need to get a bounding box to find out how close 112 and 1113 can be placed. For this we run two boards that cannot touch, scoring them by the sum of the distances they managed to get away from the starting position. This is the best they manage:

```
  0  0  0  0  0  0  0  0  0

  0  0  0  0  0  0  0  0  0

  0  0  0  0 15  0  0  0  0

  0  0 11 10  5  0  0  0  0

  0  0  0  1  4 12  0  0  0

  0  0  0  0  2  1 13  0  0

  0  0  0  0  0  0 14  0  0

  0  0  0  0  0  0  0  0  0

  0  0  0  0  0  0  0  0  0

  …

  0  0  0  0  0  0  0  0

  0  0  0  0  0  0  0  0

  0  0 17  9  0  3  1  0

  0  0  0  8  1  6  1  0

  0  0  0 16  7  0  0  0

  0  0  0  0  0  0  0  0

  0  0  0  0  0  0  0  0

```

They cannot leave 5 tiles. So if we place the initial 3 within a 20x20 (+ a padding of 4 for off-by-one-errors :-)) field centered around the 2, we either get two disconnected clusters that have a score independent on where they are exactly, or two clusters that eventually will join up. So anything up to

```
1 1 _ _ _ _ _ _ _ _ _ _ _ 1 1
_ 2 a b c d e _ e d c b a 3 1

```

will be checked with 11 spaces in between; enough that they cannot meet up.

With all this, then just recursively try out all the possibilities in a depth-first-search. Always modifying only one board, we only need memory for `a(N)` recursive steps.

OMP is only used to check the initial boards in parallel. This is far from a balanced workload; the final position needs about twice as long as the others. However, it is the easiest to implement. :-)

### The program

Compiled with `clang -O3 -o main main.c -fopenmp` and ran with `time OMP_NUM_THREADS=4 ./main`.

```
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef uint8_t mem_t;
typedef uint16_t sum_t;
#define S 64
const int startx = S/2, starty = S/2;
// for N > 5, adjust the unrolled loops in step
#define MAX_CELL 5
#define MAX_BOARDS 2

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)

const int ys[8] = {0,1,1,1,0,-1,-1,-1};
const int xs[8] = {1,1,0,-1,-1,-1,0,1};

inline
void add_sum(sum_t v, int y, int x, sum_t sum[S][S]) {
    for(int d=0;d<8;d++)
        sum[y+ys[d]][x+xs[d]] += v;
}
inline
void add_placed(sum_t v, int y, int x, mem_t placed[S][S]) {
    for(int d=0;d<8;d++)
        placed[y+ys[d]][x+xs[d]] += v;
}

typedef struct board {
  int y0, y1, x0, x1;
  mem_t b[S][S], placed[S][S];
  sum_t sum[S][S];
} board_t;

void st_print(int c, int max, board_t *b) {
    printf("%d cells, %d max\n", c, max);
    for(int y=b->y0;y<=b->y1;y++){
        for(int x=b->x0;x<=b->x1;x++) printf("%*d", 3, b->b[y][x]);
        puts("\n");
    }
}

void step(int c, mem_t max, board_t *bs, int bl, mem_t *best_max, board_t best_b[MAX_BOARDS], int optimize_spread) {
    // check board size
    for(int i=0;i<bl;i++) {
            if (bs[i].y0 < 2 || bs[i].y1 >= S - 2 || bs[i].x0 < 2 || bs[i].x1 >= S - 2) {
                    st_print(c, max, &bs[i]);
                printf("board too small %d %d %d %d", bs[i].y0, bs[i].y1, bs[i].x0, bs[i].x1);
                exit(1);
            }
    }
    // new best
    if (c == MAX_CELL) {
        int score = 0;
            if (optimize_spread) {
                    for (int i=0;i<bl;i++)
                        score += MAX(starty - bs[i].y0,
                                 MAX(bs[i].y1 - starty,
                                 MAX(startx - bs[i].x0,
                                     bs[i].x1 - startx)));
            } else {
                    score = max;
            }
            if (*best_max < score) {
                for (int i=0;i<bl;i++)
                        memcpy(&best_b[i], &bs[i], sizeof(board_t));
                *best_max = score;
            }
    }
    // place with 0 new 1-cells
    if(!optimize_spread || max != 2)
    for(int i=0;i<bl;i++) {
            board_t *b=bs+i;
            for(int y=b->y0;y<=b->y1;y++)
            for(int x=b->x0;x<=b->x1;x++)
            if(b->sum[y][x] == max + 1 && !b->b[y][x]) {
                b->b[y][x] = max + 1;
                add_sum(max+1,y,x,b->sum);
                add_placed(1,y,x,b->placed);
                int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
                b->y0 = MIN(b->y0, y-2);
                b->y1 = MAX(b->y1, y+2);
                b->x0 = MIN(b->x0, x-2);
                b->x1 = MAX(b->x1, x+2);
                step(c, max + 1, bs, bl, best_max, best_b, optimize_spread);
                b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
                add_placed(-1,y,x,b->placed);
                add_sum(-(max+1),y,x,b->sum);
                b->b[y][x] = 0;
            }
    }
    // sorry for the repetition, couldn't get clang to optimize it otherwise
    // place with 1 new 1-cells
    if(!optimize_spread || max != 2)
    if(c + 1 <= MAX_CELL)
    for(int i=0;i<bl;i++) {
            board_t *b=bs+i;
            for(int y=b->y0;y<=b->y1;y++)
            for(int x=b->x0;x<=b->x1;x++)
            if(b->sum[y][x] == (max + 1) - 1 && !b->b[y][x]) {
                for(int d1=0;d1<8;d1++) {
                    if (b->placed[y+ys[d1]][x+xs[d1]]) continue;

                    b->b[y+ys[d1]][x+xs[d1]] = 1;
                    b->b[y][x] = max + 1;
                    add_sum(max+1,y,x,b->sum);
                    add_sum(1,y+ys[d1],x+xs[d1],b->sum);
                    add_placed(1,y,x,b->placed);
                        int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
                        b->y0 = MIN(b->y0, y-2);
                        b->y1 = MAX(b->y1, y+2);
                        b->x0 = MIN(b->x0, x-2);
                        b->x1 = MAX(b->x1, x+2);
                        step(c + 1, max + 1, bs, bl, best_max, best_b, optimize_spread);
                        b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
                    add_placed(-1,y,x,b->placed);
                    add_sum(-(max+1),y,x,b->sum);
                    add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
                    b->b[y+ys[d1]][x+xs[d1]] = 0;
                    b->b[y][x] = 0;
                }
            }
    }
    // place with 2 new 1-cells
    if(!optimize_spread || max != 2)
    if(c + 2 <= MAX_CELL)
    for(int i=0;i<bl;i++) {
            board_t *b=bs+i;
            for(int y=b->y0;y<=b->y1;y++)
            for(int x=b->x0;x<=b->x1;x++)
            if(b->sum[y][x] == (max + 1) - 2 && !b->b[y][x]) {
                for(int d1=0;d1<8-1;d1++) {
                    if (b->placed[y+ys[d1]][x+xs[d1]]) continue;
                for(int d2=d1+1;d2<8;d2++) {
                    if (b->placed[y+ys[d2]][x+xs[d2]]) continue;

                    b->b[y+ys[d1]][x+xs[d1]] = 1;
                    b->b[y+ys[d2]][x+xs[d2]] = 1;
                    b->b[y][x] = max + 1;
                    add_sum(max+1,y,x,b->sum);
                    add_sum(1,y+ys[d1],x+xs[d1],b->sum);
                    add_sum(1,y+ys[d2],x+xs[d2],b->sum);
                    add_placed(1,y,x,b->placed);
                        int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
                        b->y0 = MIN(b->y0, y-2);
                        b->y1 = MAX(b->y1, y+2);
                        b->x0 = MIN(b->x0, x-2);
                        b->x1 = MAX(b->x1, x+2);
                        step(c + 2, max + 1, bs, bl, best_max, best_b, optimize_spread);
                        b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
                    add_placed(-1,y,x,b->placed);
                    add_sum(-(max+1),y,x,b->sum);
                    add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
                    add_sum(-1,y+ys[d2],x+xs[d2],b->sum);
                    b->b[y+ys[d1]][x+xs[d1]] = 0;
                    b->b[y+ys[d2]][x+xs[d2]] = 0;
                    b->b[y][x] = 0;
                }
                }
            }
    }
    // place with 3 new 1-cells
    if(c + 3 <= MAX_CELL)
    for(int i=(optimize_spread && max == 2);i<bl;i++) {
            board_t *b=bs+i;
            for(int y=b->y0;y<=b->y1;y++)
            for(int x=b->x0;x<=b->x1;x++)
            if(b->sum[y][x] == (max + 1) - 3 && !b->b[y][x]) {
                for(int d1=0;d1<8-2;d1++) {
                    if (b->placed[y+ys[d1]][x+xs[d1]]) continue;
                for(int d2=d1+1;d2<8-1;d2++) {
                    if (b->placed[y+ys[d2]][x+xs[d2]]) continue;
                for(int d3=d2+1;d3<8;d3++) {
                    if (b->placed[y+ys[d3]][x+xs[d3]]) continue;

                    b->b[y+ys[d1]][x+xs[d1]] = 1;
                    b->b[y+ys[d2]][x+xs[d2]] = 1;
                    b->b[y+ys[d3]][x+xs[d3]] = 1;
                    b->b[y][x] = max + 1;
                    add_sum(max+1,y,x,b->sum);
                    add_sum(1,y+ys[d1],x+xs[d1],b->sum);
                    add_sum(1,y+ys[d2],x+xs[d2],b->sum);
                    add_sum(1,y+ys[d3],x+xs[d3],b->sum);
                    add_placed(1,y,x,b->placed);
                        int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
                        b->y0 = MIN(b->y0, y-2);
                        b->y1 = MAX(b->y1, y+2);
                        b->x0 = MIN(b->x0, x-2);
                        b->x1 = MAX(b->x1, x+2);
                        step(c + 3, max + 1, bs, bl, best_max, best_b, optimize_spread);
                        b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
                    add_placed(-1,y,x,b->placed);
                    add_sum(-(max+1),y,x,b->sum);
                    add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
                    add_sum(-1,y+ys[d2],x+xs[d2],b->sum);
                    add_sum(-1,y+ys[d3],x+xs[d3],b->sum);
                    b->b[y+ys[d1]][x+xs[d1]] = 0;
                    b->b[y+ys[d2]][x+xs[d2]] = 0;
                    b->b[y+ys[d3]][x+xs[d3]] = 0;
                    b->b[y][x] = 0;
                }
                }
                }
            }
    }
}

void set_starting_board(board_t* b, int i) {
    int x0 = startx, y0 = starty;
    b->b[y0][x0] = 2;
    if (i == 0) b->b[y0-1][x0-1] = 1,
                b->b[y0+1][x0+1] = 1;
    if (i == 1) b->b[y0-1][x0-1] = 1,
                b->b[y0][x0+1] = 1;
    if (i == 2) b->b[y0][x0-1] = 1,
                b->b[y0][x0+1] = 1;
    if (i == 3) b->b[y0-1][x0] = 1,
                b->b[y0][x0+1] = 1;
    if (i == 4) b->b[y0-1][x0-1] = 1,
                b->b[y0-1][x0+1] = 1;
    if (i == 5) b->b[y0-1][x0] = 1,
                b->b[y0-1][x0+1] = 1;

    for(int y=1;y+1<S;y++)
    for(int x=1;x+1<S;x++)
    for(int yd=-1;yd<=1;yd++)
    for(int xd=-1;xd<=1;xd++)
    if(yd!=0||xd!=0)
        b->sum[y][x] += b->b[y+yd][x+xd];
    for(int y=1;y+1<S;y++)
    for(int x=1;x+1<S;x++)
    for(int yd=-1;yd<=1;yd++)
    for(int xd=-1;xd<=1;xd++)
        b->placed[y][x] += b->b[y+yd][x+xd] > 1;

}

int get_bounding_box() {
    int x0 = startx, y0 = starty;
    board_t best_b[6][3] = {0};
    mem_t best_max[6] = {0};

 #pragma omp parallel for
    for(int i=0;i<6;i++) {
        board_t bs[] = {(board_t){y0 - 3, y0 + 3, x0 - 3, x0 + 3, {0}, {0}, {0}},
                            (board_t){y0, y0, x0, x0, {0}, {0}, {0}}};
            set_starting_board(&bs[0], i);
        step(2, 2, bs, 2, &best_max[i], best_b[i], 1);
    }

    int best_i=0, mm = 0;
    for(int i=0;i<6;i++)
        if (best_max[i] > mm)
            mm = best_max[i],
            best_i = i;
    printf("most spread of distant 112 and 1113: %d\n", best_max[best_i]);
    st_print(MAX_CELL, best_max[best_i], &best_b[best_i][0]);
    st_print(MAX_CELL, best_max[best_i], &best_b[best_i][1]);

    return best_max[best_i] + 4;
}

int main(int argc, char **argv) {
    int bb = get_bounding_box();

    int x0 = startx, y0 = starty;
    board_t best_b[6][3] = {0};
    mem_t best_max[6] = {0};

 #pragma omp parallel for
    for(int i=0;i<6;i++) {
        board_t bs[] = {(board_t){y0 - bb, y0 + bb, x0 - bb, x0 + bb, {0}, {0}, {0}},};
            set_starting_board(&bs[0], i);
        step(2, 2, bs, 1, &best_max[i], best_b[i], 0);
    }

    int best_i=0, mm = 0;
    for(int i=0;i<6;i++)
        if (best_max[i] > mm)
            mm = best_max[i],
            best_i = i;
    st_print(MAX_CELL, best_max[best_i], &best_b[best_i][0]);

    return 0;
};

```
> 11 votes

# Answer
# C (Perl) n=6

My first^Wsecond pass at this is available on github ; I think this should in principle be able to calculate up to a(8), but that'll take a while even now it has been recoded in C.

On my machine it takes 42s for a(4) and 14ks for a(5), traversing 63,200,517 and 18,371,175,865 board positions respectively; rewriting in C gave about a 250x speedup from the initial Perl prototype.

Solution found for a(5) = 49:

```
  .  . 39  .  .  . 47  . 49
 46 20 19  . 40  . 23 24 25
 26  .  1 18  . 22  .  1  .
  .  6  2  7  8  . 14  . 42
  . 28  3  1 38 13 27 41  .
  . 48 17  4  5  .  .  .  .
  .  .  .  9 43 15 31  .  .
  .  . 30  . 10  . 16  .  .
  .  .  . 21 11  1 29 45  .
  .  .  . 32  . 12  .  .  .
  . 34 33  . 44  .  .  .  .
 35  1  .  .  .  .  .  .  .
  . 36 37  .  .  .  .  .  .

```

(Oh, that's a symmetry of xash's solution, I somehow expected it to be different.)

Confirming a(6) = 60 took around 10 CPU-weeks (manually sharded) and traversed 4.57e12 positions. Solution found:

```
  . 56 42  . 60  .  .  .  .  .  .  .  .  .
  .  . 14 28 32  .  .  .  .  .  .  .  .  .
  . 29 10  4  . 35  .  .  .  .  .  .  .  .
  . 44  5  1  3 46  .  .  .  .  .  .  .  .
  .  .  . 31  2  6  . 37  .  .  .  .  .  .
 55  .  . 11  9  1  7 30  .  .  .  .  .  .
 54  1 12 45  . 25  8 15  .  .  .  .  .  .
 27 26 13  .  . 33  . 40 16 34 51  .  .  .
 53  . 39 52  .  .  .  .  1 17  .  .  .  .
  .  .  .  .  .  .  . 57 18  . 36  .  .  .
  .  .  .  .  .  .  .  . 38 19  .  .  .  .
  .  .  .  .  .  .  .  . 58  1 20 41  .  .
  .  .  .  .  .  .  .  . 59  . 21  .  . 47
  .  .  .  .  .  .  .  .  .  . 43 22 23 24
  .  .  .  .  .  .  .  .  .  .  .  .  1 48
  .  .  .  .  .  .  .  .  .  .  . 50 49  .

```

Finding a(7) would, by extrapolation, take 200-250 times as long as a(6). I don't plan to attempt this.

The approach is a) to insert the **1**s lazily as needed, and b) to store unconnected groups separately, coalescing them as needed.

Extending beyond a(8) would require allowing for the possibility that we need to simultaneously coalesce 3 or more groups. I won't bother trying to solve that unless I get the speed of a(8) down to under a day or so.

The core work is done by the Board-\>try function (C: try\_board), which tries each possible way to place the next number in the current board, then recurses.

The Group-\>coalesce (C: coalesce\_group) function was the last and trickiest part to write: given two groups, the location within each that will form the common point at which the new value will be inserted, and the number of additional **1**s that must be placed around it, this algorithm:

* fixes the orientation of the first group, and tries out each of the 8 possible orientations of the second group;
* first checks the immediate neighbourhood of the common location, looking for orientations that allow the two groups to coexist and leave room for enough additional **1**s;
* then tries to overlay one group on the other, checking for further clashes;
* finally generates the k of n combinations of the n available cells around the common location into which the k additional **1**s requested can be placed.

The hardest bit is going to be finding bugs, since there are so few data points to check against. I've added more tests, but I don't have confidence that I've found all bugs.

Hugo

\[2020-10-10: added precise timings and position counts\]

\[2020-10-13: progress in C, a(5) found\]

\[2020-11-05: a(6) = 60 confirmed\]
> 10 votes

---
Tags: code-challenge, sequence, combinatorics, grid
---


title: Is it a weak prime?

text:
# Question
Title: Is it a weak prime?
A prime is weak if the closest other prime is smaller than it. If there is a tie the prime is not weak.

For example **73** is a weak prime because **71** is prime but **75** is composite.

## Task

Write some computer code that when given a prime greater than **2** as input will determine if it is a weak prime. This is a standard so you should output two unique values for each of the two cases (e.g. `weak` and `not weak`).

This is so standard rules for the tag apply.

## OEIS

Here are the first 47 weak primes:

```
3, 7, 13, 19, 23, 31, 43, 47, 61, 73, 83, 89, 103, 109, 113, 131, 139, 151, 167, 181, 193, 199, 229, 233, 241, 271, 283, 293, 313, 317, 337, 349, 353, 359, 383, 389, 401, 409, 421, 433, 443, 449, 463, 467, 491, 503, 509, 523, 547, 571, 577, 601, 619, 643, 647

```

Here is the OEIS for weak primes (should return `weak`) OEIS A051635

Here is the OEIS for balanced primes (should return `not weak`) OEIS A006562

Here is the OEIS for strong primes (should return `not weak`) OEIS A051634

# Answer
# Jelly, 7 bytes

```
Æn+Æp>Ḥ

```

Try it online!

### Explanation

```
           See if
Æn         the next prime
  +Æp      plus the previous prime
     >Ḥ    is greater than 2n

```

As a bonus, changing `>` to `=` or `<` checks for balanced and strong primes, respectively.
> 26 votes

# Answer
## Mathematica, 24 bytes

```
n=NextPrime;2#+n@-#<n@#&

```

The `NextPrime` built-in can be (ab?)used to compute the previous prime by feeding it a negative argument.
> 12 votes

# Answer
# Jelly, 9 bytes

```
ḤÆRạÞ⁸ḊḢ>

```

Returns `1` for weak and `0` for not weak or balanced (returns `1` for an input of `2`)

**Try it online!**

### How?

```
ḤÆRạÞ⁸ḊḢ> - Link: prime number > 2, p
Ḥ         - double -> 2*p
 ÆR       - yield primes between 2 and 2*p inclusive
     ⁸    - chain's left argument, p
    Þ     - sort by:
   ạ      -   absolute difference (i.e. distance from p)
      Ḋ   - dequeue (removes p from the list, since it has distance zero)
       Ḣ  - head (gives us the nearest, if two the smallest of the two)
        > - greater than p?

```
> 6 votes

# Answer
# PHP, 69 bytes

prints one for weak prime and nothing for not weak prime

```
for(;!$t;$t=$d<2)for($n=$d=$argn+$i=-$i+$w^=1;$n%--$d;);echo$n<$argn;

```

Try it online!
> 5 votes

# Answer
# Octave, ~~93~~ 84 bytes

*Thanks to @LuisMendo and @rahnema1 for saving bytes!*

```
function r=f(x);i=j=x;do--i;until(i<1|isprime(i));do++j;until(isprime(j));r=x-i<j-x;

```

Try it online!
> 3 votes

# Answer
# MATL, 13 bytes

```
qZq0)G_Yq+GE>

```

This outputs `1` if weak, `0` otherwise.

Try it online!

### Explanation

```
q      % Implicit input, Subtract 1
Zq     % Vector of primes up to that
0)     % Get last one
G      % Push input again
_Yq    % Next prime
+      % Add
G      % Push input
E      % Multiply by 2
>      % Greater than? Implicit display

```
> 3 votes

# Answer
# Maxima, 42 bytes

```
f(n):=is(n-prev_prime(n)<next_prime(n)-n);

```

Try it online!
> 3 votes

# Answer
# GNU APL 1.2, 78 bytes

```
∇f N
X←(R←(~R∊R∘.×R)/R←1↓⍳N×2)⍳N
(|R[X-1]-N)<|R[X+1]-N
∇

```

`∇f N` declares a function that takes an argument.

`(~R∊R∘.×R)/R←1↓⍳N×2` gives a list of all the primes from 2 to twice the argument. I'm assuming that the next prime is less than twice the original. If this is untrue, `N*2` gives N squared and takes the same number of bytes (hopefully that's big enough to exceed the next prime). (See Wikipedia's explanation for how the prime-finding works)

`X←(R←(...))⍳N` assigns that list to vector `R` (overwriting its previous contents), finds the index of the original prime `N` in that list, and then assigns that index to `X`.

`|R[X-1]-N` computes the difference between the previous prime (because `R` contains the primes, the `X-1`th element is the prime before `N`) and `N` and then takes the absolute value (APL operates right-to-left).

`|R[X+1]-N` does the same, but for the next prime.

`(|R[X-1]-N)<|R[X+1]-N` prints 1 if the previous prime is closer to the original than the next prime and 0 otherwise. Parentheses are needed for precedence.

ends the function.
> 3 votes

# Answer
# Jelly, 9 bytes

```
Æp;;ÆnI</

```

Try it online!
> 2 votes

# Answer
# Pyth, 15 bytes

```
>-fP_ThQfPT_tQy

```

Try it here.

Uses Pietu1998's algorithm.
> 2 votes

# Answer
# Perl 6, 41 bytes

```
{[>] map ->\n{$_+n,*+n...&is-prime},1,-1}

```

Try it online!

`$_` is the argument to the function. The mapping function `-> \n { $_ + n, * + n ... &is-prime }` takes a number `n` and returns a sequence of numbers `$_ + n, $_ + 2*n, ...` that ends when it reaches a prime number. Mapping this function over the two numbers `1` and `-1` produces a sequence of two sequences; the first starts with `$_ + 1` and ends with the first prime number greater than `$_`, and the second starts with `$_ - 1` and ends with the first prime number less than `$_`. `[>]` reduces this two-element list with the greater-than operator, returning true if the first sequence is greater (ie, longer) than the second.
> 2 votes

# Answer
# Python 2, ~~122~~ ~~108~~ ~~103~~ ~~94~~ 92 bytes

```
def a(n):
 r=[2];x=2
 while r[-1]<=n:x+=1;r+=[x]*all(x%i for i in r)
 return sum(r[-3:])>3*n

```

Try it online!

Uses Pietu's idea... and then saved 28 bytes by golfing shorter prime list iterators; then 2 more by replacing `-3*n>0` with `>3*n` (d'oh!)
> 2 votes

# Answer
## Python 2.7 - 120 bytes

```
from math import*
i=lambda x:factorial(x-1)%x==x-1
def f(n,c):return 1 if i(n-c)>i(n+c) else 0 if i(n+c)>0 else f(n,c+1)

```

Since python doesn't have a built-in is prime function, we can use Wilson's theorem to get a nice short prime checker. Wilson's theorem states that a number is prime if and only if (n-1)! is congruent to -1 mod(n). Hence the function i will return 1 if the number is prime and 0 if it's not. Following that the f function will determine if the next prime from that number occurs first when incremented down rather than incremented up. If neither of the incremented numbers prime, it's just recursively called again.

Some example I/O

```
f(3,1)
1
f(15,1)
0

```
> 2 votes

# Answer
# Regex (most flavors), 47 bytes

```
^(?=(x*)(?!(x+)(\2\2x)+$)\1)x+(?!(xx+)\4+$)\1\1

```

Try it online!

Takes input in unary. Outputs a match for weak primes, no match for non-weak primes. Works in ECMAScript, Perl, PCRE, Python, Ruby.

Explanation:

Let N be the input, A the closest prime \< N, and B the closest prime \> N. The main difficulty of a regex approach to this challenge is that we can’t represent numbers greater than the input, like B. Instead, we find the smallest b such that 2b + 1 is prime and 2b + 1 \> N, which ensures 2b + 1 = B.

```
(?=
  (x*)              # \1 = N - b, tail = b
  (?!(x+)(\2\2x)+$) # Assert 2b + 1 is prime
  \1                # Assert b ≥ \1 (and thus 2b + 1 > N)
)

```

Then, note that we don’t actually need to find A. As long as *any* prime \< N is closer to N than B, N is a weak prime.

```
x+                  # tail iterates over integers < N
(?!(xx+)\4+$)       # assert tail is prime
\1\1                # assert tail ≥ 2 * \1 (and thus tail + B > 2N)

```
> 2 votes

# Answer
# Octave, 53 bytes

```
@(n)diff(list_primes(h=nnz(primes(n))+1)(h-2:h),2)>0

```

Try it online!
> 1 votes

# Answer
# JavaScript ES6, ~~162~~ 154 bytes

8 bytes save based on *Jörg Hülsermann*'s trick "print nothing in one case". No need to `?"Y":"N"` after `one<two`

```
var isWeak=

a=>{p=[2];i=0;f=d=>{j=p[i];l:while(j++){for(x=0;p[x]*p[x]<=j;x++){if(j%p[x]==0){continue l}}return p[++i]=j}};while(p[i]<a+1){f()};return a*2<p[i]+p[i-2]}

[43,//true
53,//false
7901,//false
7907,//true
1299853,//true
1299869//false
].forEach(n=>{console.log(n,isWeak(n))})
```
> 1 votes

# Answer
# 05AB1E, 17 bytes

```
[<Dp#]¹[>Dp#]+¹·›

```

Try it online!

Uses Pietu1998's algorithm.
> 0 votes

# Answer
# Python 3, 149 bytes

```
f=lambda n,k=1,P=1:n*[0]and P%k*[k]+f(n-P%k,k+1,P*k*k)
def a(n):p=f(n);return p.index(n)in filter(lambda i:p[i]-p[i-1]<p[i+1]-p[i],range(1,len(p)-1))

```

Try it online!

I'm using a prime generating function (top line) taken from this old stack exchange answer.
> 0 votes

# Answer
# JavaScript, 98 bytes

```
let test = _=>(o.innerHTML=f(+prime.value))
let f=

n=>{P=n=>{for(i=n,p=1;--i>1;)p=p&&n%i};a=b=n;for(p=0;!p;P(--a));for(p=0;!p;P(++b));return n-a<b-n}
```

```
Enter Prime: <input id="prime">
<button type="button" onclick="test()">test if weak</button>
<pre id="o"></pre>
```

**Less Golphed**

```
n=>{
   P=  // is a Prime greater than 1, result in p
       n=>{
           for(i=n,p=1;--i>1;)
               p=p&&n%i
       };

   a=b=n; // initialize lower and upper primes to n
   for(p=0;!p;P(--a)); // find lower,
   for(p=0;!p;P(++b)); // find upper,
   return n-a<b-n // is weak result
}

```

Note the test code does *not* check the input "prime" is actually a prime.
> 0 votes

# Answer
# Julia 0.6, 64 bytes

```
g(x,i)=0∉x%(2:x-1)?1:1+g(x+i,i);x->g(x,1)&(g(x-1,-1)<g(x+1,1))

```
> 0 votes

# Answer
# braingasm, ~~23~~ 22 bytes

Prints `1` for weak primes and `0` for not weak.

```
;>0$+L[->+>2[>q[#:Q]]]

```

Walkthrough:

```
;                       Read a number to cell 0
 >0$+                   Go to cell 1 and copy the value of cell 0
     L                  Make the tape wrap around after cell 1
      [              ]  Loop:
       ->+>               Decrease cell 1 and increase cell 0
           2[       ]     Twice do:
             >              Go to the other cell
              q[   ]        If it's prime:
                #:Q         Print the current cell number and quit

```
> 0 votes

# Answer
# Python 2, 81 bytes

```
n=input()
a=b=c=i=2;p=1
while b<n:
 p*=i;i+=1
 if p*p%i:a,b,c=b,c,i
print a+c>2*b

```

Try it online!

Uses Wilson's theorem for the primality test.
> 0 votes

# Answer
# Husk, 15 bytes

```
>D¹Σ§e₁←₁→
ḟṗt¡

```

Try it online!
> 0 votes

---
Tags: code-golf, number-theory, decision-problem, primes
---


title: Generating Fermat primes

text:
# Question
Title: Generating Fermat primes
Given a number n, print the nth **prime** Fermat number, where the Fermat numbers are of the form 22k+1. This code should theoretically work for any n (i.e. don't hardcode it), although it is not expected to terminate for n \> 4. (It should **not** return 4294967297 for n=5, as 4294967297 is not a prime number.)

Do note that while all Fermat primes are of the form 22n+1, not all numbers of the form 22n+1 are prime. The goal of this challenge is to return the n-th **prime.**

# Test cases

```
0 -> 3
1 -> 5
2 -> 17
3 -> 257
4 -> 65537

```

# Rules

* Standard loopholes are disallowed.
* 0-indexing and 1-indexing are both acceptable.
* This is , lowest byte-count wins.

Related: Constructible n-gons

# Answer
# Python 2, 53 bytes

```
k=input();F=2
while k:F*=F;k-=3**(F/2)%-~F/F
print-~F

```

Try it online!

Uses Pépin's test.

---

**Python 2, 54 bytes**

```
f=lambda k,F=4:k and f(k-3**(F/2)%-~F/F,F*F)or F**.5+1

```

Try it online!
> 6 votes

# Answer
# Jelly, ~~13~~ 11 bytes

```
ÆẸ⁺‘©ÆPµ#ṛ®

```

Uses 1-based indexing.

Try it online!

### How it works

```
ÆẸ⁺‘©ÆPµ#ṛ®  Main link. No argument.

        #    Read an integer n from STDIN and call the chain to the left with
             arguments k = 0, 1, 2, ... until n matches were found.
ÆẸ           Find the integer with prime exponents [k], i.e., 2**k.
  ⁺          Repeat the previous link, yielding 2**2**k.
   ‘         Increment, yielding 2**2**k+1 and...
    ©        copy the result to the register.
     ÆP      Test the result for primality.
          ®  Yield the value from the register, i.e., the n-th Fermar prime.
         ṛ   Yield the result to the right.

```
> 3 votes

# Answer
# Perl 6,  ~~45~~  42 bytes

```
{({1+[**] 2,2,$++}...*).grep(*.is-prime)[$_]}

```

Try it

```
{({1+2**2**$++}...*).grep(*.is-prime)[$_]}

```

Try it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  (  # generate a sequence of the Fermat numbers

    {
      1 +
      2 ** 2 **
        $++            # value which increments each time this block is called
    }
    ...                # keep generating until:
    *                  # never stop

  ).grep(*.is-prime)\  # reject all of the non-primes
  [$_]                 # index into that sequence
}

```
> 2 votes

# Answer
# Mathematica, 56 bytes

```
(t=n=0;While[t<=#,If[(PrimeQ[s=2^(2^n)+1]),t++];n++];s)&

```

Try it online!
> 1 votes

# Answer
# Dyalog APL (29 Characters)

I'm almost certain this can be improved.

```
{2=+/0=(⍳|⊢)a←1+2*2*⍵:a⋄∇⍵+1}

```

This is a recursive function which checks the number of divisors of 1+2^2^⍵, where ⍵ is the right argument of the function. If the number of divisors is 2, the number is prime, and it returns it, otherwise, it calls the function again with ⍵+1 as a right argument.

## Example

```
{2=+/0=(⍳|⊢)a←1+2*2*⍵:a ⋄ ∇ ⍵+1}¨⍳4
      5 17 257 65537

```

Here I call the function on each of ⍳4 (the numbers 1-4). It applies it to every number in turn.
> 1 votes

# Answer
# Pyth, 14 bytes

```
e.f&P_ZsIltZQ3

```

Try it online!

Uses 1-indexing.
> 0 votes

# Answer
# Pyth, 14 bytes

```
Lh^2^2byfP_yTQ

```

Try online.

Main idea "borrowed" from xnor's answer in another question

```
Lh^2^2byfP_yTQ

L                    define a function with name y and variable b, which:
 h^2^2b                returns 1+2^2^b
       y             call the recently defined function with argument:
        f    Q         the first number T >= Q (the input) for which:
         P_yT            the same function with argument T returns a prime
                     and implicitly print

```
> 0 votes

# Answer
# 05AB1E, 8 bytes

### Code:

Results are 1-indexed.

```
µN<oo>Dp

```

Uses the **05AB1E** encoding. Try it online!

### Explanation:

```
µ              # Run the following n succesful times..
 N             #   Push Nn
  oo           #   Compute 2 ** (2 ** n)
    >          #   Increment by one
     D         #   Duplicate
      p        #   Check if the number is prime
               # Implicit, output the duplicated number which is on the top of the stack

```
> 0 votes

# Answer
# Javascript, ~~12~~ 46 bytes

```
k=>eval('for(i=n=2**2**k+1;n%--i;);1==i&&n')

```

Most of the code is taken up by the prime check, which is from here.
> 0 votes

# Answer
# Haskell, 61 bytes

```
p n=2^2^n;f=(!!)[p x+1|x<-[0..],all((>)2.gcd(p x+1))[2..p x]]

```

Try it online!

0-based index

**Explanation**

```
p n=2^2^n;                                          -- helper function
                                                    -- that computes what it says
f=                                                  -- main function
  (!!)                                              -- partially evaluate
                                                    -- index access operator
      [p x+1|                                       -- output x-th fermat number
             x<-[0..],                              -- try all fermat number indices
                      all                 [2..p x]  -- consider all numbers smaller F_x
                                                    -- if for all of them...
                         ((>)2                      -- 2 is larger than...
                              .gcd(p x+1))          -- the gcd of F_x
                                                    -- and the lambda input
                                                    -- then it is a Fermat prime!
                                                  ]

```
> 0 votes

# Answer
# Husk, 11 bytes

```
!fṗmȯ→‼`^2N

```

Try it online!
> 0 votes

# Answer
# GolfScript, 26 bytes

```
~3\{{(.*).,(;{*}*)1$%}do}*

```

Try it online!

0-indexed

```
~                            # Parse n to a number
 3                           # Push 3
  \{                    }*   # Execute this block n times, this block gets the next Fermat prime
    {                }do     # While the number is composite
     (.*)                    # Go to the next Fermat number
         .,(;                # Make an array from 1 to (F_n)-1
             {*}*            # Multiply the numbers to get ( (F_n)-1 )!
                 )           # Increment it
                  1$%        # This will be 0 iff the Fermat number is prime

```

The primality test used here is Wilson's theorem.
> 0 votes

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


title: Circular primes

text:
# Question
Title: Circular primes
Given a number determine if it is a circular prime.

A circular prime is a prime where if you rotate the digits you still get prime numbers. 1193 is circular prime because 1931 and 9311 and 3119 are all primes.

```
Input:          Output:
1193            circular
11939           circular
1456            nothing
193939          circular
1111111         nothing
7               circular
23              nothing

```

Shortest code wins.

# Answer
### GolfScript, 47 characters

```
:s,,{)s/(+~:P{(.P\%}do(},!"nothing
circular"n/=

```

Input must be given on STDIN without trailing newline (online example).
> 4 votes

# Answer
# J, 47 chars (w/ formatted output)

```
('nothing';'circular'){~*/1&p:".(|."0 1~i.&#)":

```

# J, 23 chars (boolean only)

```
*/1&p:".(|."0 1~i.&#)":

```

`":` is a string conversion; `i.&#` produces a range of integers \[0,len), and `|."0 1~` is a rotation of the string by each successive integer of the range.

`".` converts the list of rotations back into numbers, `1&p:` converts the list of numbers into booleans (i.e. "prime?" predicate), and `*/` is a multiply reduce over the booleans (i.e. and).
> 8 votes

# Answer
## Python, 106 chars

```
p=input();n=`p`
for i in n:
 n=n[1:]+n[0];e=2
 while`e`!=n:p*=int(n)%e;e+=1
print'cniortchuilnagr'[p<1::2]

```
> 7 votes

# Answer
# Mathematica ~~62~~ 61

```
f@s_ := And @@ PrimeQ[FromDigits@StringRotateLeft[s, #] & /@ Range@9]

```

**Usage**

```
f["1193"]

```

> True

```
f["11939"]

```

> True

```
f["1456"]

```

> False

```
f["193939"]

```

> True

```
f["1111111"]

```

> False

```
f["7"]

```

> True

```
f["23"]

```

> False
> 7 votes

# Answer
## Ruby, ~~110~~ 109 chars

```
require'mathn'
x=gets.chop.split''
puts (0..x.size).all?{|n|x.rotate(n).join.to_i.prime?}?:circular:'nothing'

```
> 5 votes

# Answer
## Mathematica, ~~75~~ 64

```
And@@PrimeQ[FromDigits/@NestList[RotateLeft,IntegerDigits@#,9]]&

```
> 5 votes

# Answer
## R, 139

```
a=scan()
p=0
A=nchar(a)
S=substr
for(i in 1:A){b=as.integer(paste0(S(a,i+1,A),S(a,1,i)));p=p+!sum(!b%%1:b)<3}
c('nothing','circular')[!p+1]

```
> 3 votes

# Answer
# Python3.3, 160C

```
def m():
 s=input()
 r=range
 for i in r(len(s)):
  a=int(s)
  if all(a%i for i in r(2,a)):return 0
  s=s[1:]+s[:1]
 return 1
print("cniortchuilnagr"[m()::2])

```
> 3 votes

# Answer
# Smalltalk, 195 chars

```
[:x|r:=[:n|(n\\10)*(10 raisedTo:n log floor)+(n//10)].s:=OrderedCollection with:x.[(m:=r value:s last)=x]whileFalse:[s add:m].^(s allSatisfy:[:each|each isPrime])ifTrue:['circular']ifFalse:['nothing']]

```

formatted

```
[:x|
  r:=[:n|(n\\10)*(10 raisedTo:n log floor)+(n//10)].
  s:=OrderedCollection with:x.
  [(m:=r value:s last)=x]whileFalse:[s add:m].
  ^(s allSatisfy:[:each|each isPrime])ifTrue:['circular']ifFalse:['nothing']]

```
> 3 votes

# Answer
# APL, 53

```
'nothing' 'circular'[1+^/{⌊/⍵|⍨1↓⍳⍵-1}¨⍎¨{⍵⌽∆}¨⍳⍴∆←⍞]

```
> 3 votes

# Answer
# Japt, 23 bytes

Would obviously be a hell of a lot shorter without the unnecessarily strict output requirement, which accounts for more than half the score here.

```
ÆìéX jÃ×g`Í(ˆg circÔ³`¸

```

Try it (includes all test cases)

```
ÆìéX jÃ×g`...`¸     :Implicit input of integer U
Æ                   :Map each X in the range [0,U)
 ì                  :   Convert U to digit array
  éX                :   Rotate right X times and convert back to integer
     j              :  Is prime?
      Ã             :End map
       ×            :Reduce by multiplication
        g           :Index into (0-based)
         `...`      :  Compressed string "circular nothing"
              ¸     :  Split on spaces

```
> 3 votes

# Answer
# Husk, ~~22~~ 19 bytes

```
?¨ÿċ◊¨¨ø±¨ΛoṗdSṀṙŀd

```

Try it online!

-3 bytes from Jo King. (simplified using )
> 2 votes

# Answer
# 05AB1E, 7 6 bytes

*-1 thanks to @ovs!*

```
gL._pP

```

Outputs `1` if a circular prime, and `0` if not! :D

Try it online!

This is actually my first effortful code answer in this site! **Yey!**

## How?

```
g         # Get the number of digits in the input number.
 L        # Push a list of all numbers from 1 to the length.
  ._      # For each number 'n' in the list, rotate the input to to the left n times and push a list of all outcomes.
    p     # Is each rotation a prime? If prime, convert that number to 1, else convert it to 0.
     P    # Push the product of all 1's or 0's (if a rotation is not prime, the product should be zero).
          # Print the product automatically.

```

---

# 05AB1E, 17 16 bytes

*Again -1 thanks to @ovs!*

```
gL._pP“‹ë“si“ÒŽ“

```

This code follows the output standard suggested by the test cases. I wrote this just in case my previous answer is invalid. If it is not, please count 6B as my score!

Try it online!

## How again?

```
gL._pP              # Works just like the previous answer.
      “‹ë“          # Push the string "nothing" from the 05AB1E dictionary.
          s         # Bring back the number output again.
           i        # If the number is 1...
            “ÒŽ“    # Push the string "circular" again from the 05AB1E dictionary.

```

Thanks to @Kevin Cruijssen's tip on compressing strings! :)

*Edit:* Wow, I noticed that both of my answers are currently the shortest (during the time of writing). That is kind of ironic for a first effortful answer. That means I won!
> 2 votes

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


title: Find a divisibility pattern

text:
# Question
Title: Find a divisibility pattern
## Background

Sometimes when I'm golfing a program, I'm presented with the following situation: I have an integer value \\$x\\$ on some fixed interval \\$\[a, b\]\\$, and I'd like to test whether it's in some fixed subset \\$S \subset \[a, b\]\\$ with as few bytes as possible. One trick that sometimes works in a language where nonzero integers are truthy is finding small integers \\$n\\$ and \\$k\\$ such that \\$x \in S\\$ holds precisely when \\$x + k\\$ doesn't divide \\$n\\$, because then my test can be just `n%(x+k)`. In this challenge your task is to compute the minimal \\$n\\$ and \\$k\\$ from the fixed data.

## The task

Your inputs are a number \\$b\\$ and a set \\$S\\$ of integers between \\$1\\$ and \\$b\\$ inclusive (we assume \\$a = 1\\$ for simplicity), in any reasonable format. You may take the complement of \\$S\\$ if you want. If you take \\$S\\$ as a list, you can assume it's sorted and duplicate-free. You can also assume \\$b\\$ is at most the number of bits in an integer and take \\$S\\$ as a bitmask if you want.

Your output is the lexicographically smallest pair of integers \\$(n,k)\\$ with \\$n \geq 1\\$ and \\$k \geq 0\\$ such that for each \\$1 \leq x \leq b\\$, \\$k+x\\$ divides \\$n\\$ if and only if \\$x\\$ is *not* an element of \\$S\\$. This means that \\$n\\$ should be minimal, and then \\$k\\$ should be minimal for that \\$n\\$. Output format is also flexible.

Note that you only have to consider \\$k \leq n\\$, because no \\$k+x\\$ can divide \\$n\\$ when \\$k \geq n\\$.

The lowest byte count in each language wins.

## Example

Suppose the inputs are \\$b = 4\\$ and \\$S = \[1,2,4\]\\$. Let's try \\$n = 5\\$ (assuming all lower values have been ruled out).

* The choice \\$k=0\\$ doesn't work because \\$k+1 = 1\\$ divides \\$5\\$ but \\$1 \in S\\$.
* The choice \\$k=1\\$ doesn't work because \\$k+3 = 4\\$ does not divide \\$5\\$ but \\$3 \notin S\\$.
* The choice \\$k=2\\$ works: \\$k+1 = 3\\$, \\$k+2 = 4\\$ and \\$k+4 = 6\\$ don't divide \\$5\\$, and \\$k+3 = 5\\$ divides \\$5\\$.

## Test cases

```
b S -> n k
1 [] -> 1 0
1 [1] -> 1 1
2 [] -> 2 0
2 [1] -> 3 1
2 [2] -> 1 0
2 [1,2] -> 1 1
4 [1,2,4] -> 5 2
4 [1,3,4] -> 3 1
5 [1,5] -> 168 4
5 [2,5] -> 20 1
5 [3,4] -> 6 1
5 [2,3,4,5] -> 1 0
6 [1] -> 3960 6
8 [2,3,6,7] -> 616 3
8 [1,3,5,7,8] -> 105 1
8 [1,2,3,4,5] -> 5814 11
9 [2,3,5,7] -> 420 6
14 [3,4,6,7,8,9,10,12,13,14] -> 72 7

```

# Answer
> 7 votes
# 05AB1E, ~~21~~ ~~20~~ ~~19~~ 18 bytes

Thanks to Kevin Cruijssen for -1 byte!
-1 byte inspired by xash's Brachylog answer!

```
[¼¾ƒ²L¾ÑN-K¹Qi¾N‚q

```

Try it online!
or
Try most test cases! (based on the test-suite by FryAmTheEggman for this answer.)

```
            # see below for the remainder of the code
²L          # push [1 .. b]
  ¾Ñ        # push the divisors of n
    N-      # subtract k from each
            # this is now a list of all x in [-k+1 .. n-k] with n%(x+k)==0
      K     # remove this from [1 .. b]
       ¹Q   # is this equal to S?

```

---

# 05AB1E, ~~24~~ 23 bytes

First line of input is the set \\$S\\$, second one \\$b\\$.

```
[¼¾ƒ¾¹²L‚N+Ö_O¹gªËi¾N‚q

```

Try it online!

This iterates through all possible pairs in lexicographical order and checks for each pair:

\begin{align\*} \left|S\right| &=\left|\left\\{ x \in \[1 .. b\] \mid x \\;\text{does not divide}\\; n \right\\}\right| \\\&= \left|\left\\{ x \in S \mid x \\;\text{does not divide}\\; n \right\\}\right| \end{align\*}

**Commented**:

```
[                # infinite loop
 ¼¾              # increment and push the counter (n)
   ƒ             # for N(=k) in [0 .. n]:
¾                #   push n
 ¹               #   push the first input (S)
  ²L             #   push [1 .. second input (b)]
    ‚            #   pair these two lists up
     N+          #   add current k to both lists
       Ö_        #   do they not divide n (vectorizes)
         O       #   sum both lists
          ¹g     #   push the length of S
            ª    #   append this to the list
             Ë   #   are all equal?
i                #   if this is true:
 ¾               #     push n
  N              #     push k
   ‚             #     pair n and k
    q            #     quit the program (implicit output)

```

# Answer
> 6 votes
# Haskell, 63 bytes

```
b!s=[(n,k)|n<-[1..],k<-[0..n],[x|x<-[1..b],mod n(k+x)>0]==s]!!0

```

Try it online!

# Answer
> 6 votes
# Python 3, ~~110~~ ~~91~~ 89 bytes

Saved a whopping ~~19~~ 21 bytes thanks to Jitse!!!

Blows up on TIO because of insane recursion depths! :(

```
f=lambda b,S,n=1,k=0:S==[x+1for x in range(b)if n%(k-~x)]and(n,k)or f(b,S,n+k//n,-~k%-~n)

```

Try it online!

# Answer
> 6 votes
# , ~~92~~ ~~86~~ ~~85~~ ~~83~~ 82 bytes

*Edit: -2 bytes thanks to Giuseppe, then -1 more byte thanks to Robin Ryder*

```
function(b,S)repeat for(k in 0:(F=F+1))if(all(1:b%in%S-!F%%(1:b+k)))return(c(F,k))

```

Try it online!

Tests increasing velues of n (actually defined as `F` here, to exploit its default initial value of zero), and for each one loops through all `k` and returns `F,k` if they satisfy `!F%%(x+k) != x %in% S` for all `x` in `1:b`.

Now 6 bytes shorter than my previous recursive version, *and* it can actually complete all the test cases without needing to increase the  recursion limit and allocated stack size.

# Answer
> 4 votes
# JavaScript (ES6),  ~~85 83~~  82 bytes

Expects `(b)(s)`, where `s` is a Set. Returns `[n, k]`.

```
b=>s=>{for(n=k=0;(g=x=>x&&n%(x+k)>0^s.has(x)|g(x-1))(b,k=k?k-1:++n););return[n,k]}

```

Try it online!

### Commented

```
b => s => {             // b = upper bound; s = set of integers
  for(                  // main loop:
    n = k = 0;          //   start with n = k = 0
    (                   //
      g = x =>          //   g is a recursive function taking x:
        x &&            //     stop if x = 0
        n % (x + k) > 0 //     otherwise yield 1 if x + k does not divide n
        ^ s.has(x)      //     XOR with 1 if x belongs to the set
        | g(x - 1)      //     recursive call with x - 1
    )(                  //   initial call to g:
      b,                //     start with x = b
      k =               //     update k:
        k ? k - 1       //       decrement k if it's not equal to 0
          : ++n         //       otherwise, increment n and set k to n
    );                  //   end of call to g; break if it's falsy
  );                    // end of loop
  return [n, k]         // return the result
}                       //

```

# Answer
> 4 votes
# C (gcc), ~~129~~ \\$\cdots\\$ ~~111~~ 109 bytes

```
x;s;n;k;f(b,S){for(s=n=1;s;++n)for(k=0;k++<=n&&s;)for(x=b,s=S;x--;)s-=!(n%(x+k))<<x;printf("%d %d",n-1,k-2);}

```

Try it online!

Takes \\$S\\$ as an inverted bitmask of length \\$b\\$ and outputs \\$n\\$ and \\$k\\$ to  `stdout`.

### Explanation

```
f(b,S){                  // function f takes b as an int and S as a
                         // inverted bitmask - the least significant
                         // b-bits of S are unset only if that bit position
                         // corresponds to a member of the original set S
  for(s=n=1;             // loop starting with n=1 and s temporarily
                         // set to 1 just to pass the first two loop tests
            s;           // loop until s is 0
              ++n)       // bumping n up by +1 each time
   for(k=0;              // inner loop trying values of k starting at 0
           k++           // k is  bumped up by +1 before use to offset b
                         // which will be 1 less than needed
              <=n        // loop until k is +1 greater than n
                 &&s;)   // or until we've hit our target
     for(x=b,            // another nested for loop of x starting at b-1
             s=S;        // first real init of s to input bitmask
                 x--;)   // loop from b-1 down to 0
                         // which corresponds to b down to 1
                         // since x is offset by -1
      s-=!(n%(x+k))<<x;  // subtract off from s bits corresponding to values
                         // for which n%(x+k) is false - because it's the
                         // inverted bitmask
                         // s will be 0 at the end of this most inner loop
                         // iff n and k are our minimal targets
   printf("%d %d",       // once we've discovered the smallest n and k
              n-1,       // we need to compensated for loop increments
              k-2);      // and k being offset by +1
}

```

# Answer
> 4 votes
# Jelly, 19 bytes

```
Ż⁴+þ⁸%T€i©
1ç1#‘,®’

```

A full program accepting the set, \\$S\\$, and the upper bound, \\$b\\$, which prints the variables as a list, \\$\[n,k\]\\$.

**Try it online!**

Or see the test-suite (without the two longest-running inputs).
Kindly provided by FryAmTheEggman.

### How?

```
1ç1#‘,®’ - Main Link: S, b
1        - set left to 1
  1#     - count up starting at x=left finding the first x which is truthy under:
 ç       -   call the helper Link as a dyad - f(x, S)
    ‘    - increment -> n+1
      ®  - recall the value from the register -> k+1
     ,   - pair -> [n+1, k+1]
       ’ - decrement -> [n, k]
         - implicit print

Ż⁴+þ⁸%T€i© - Link 1: potential_n, S
Ż          - zero-range -> [0..potential_n] (the potential k values)
 ⁴         - program's 4th argument, b
   þ       - table of (implicitly uses [1..b]):
  +        -   addition
    ⁸      - chain's left argument -> potential_n
     %     - modulo (vectorises)
      T€   - truthy 1-based indexes of each
        i  - first index of (S); 0 if not found
         © - copy that to the register and yield it

```

# Answer
> 3 votes
# Charcoal, ~~32~~ 29 bytes

```
Ｗ¬№ωθ≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κωＩ⟦Ｌυ⌕ωθ

```

Try it online! Link is to verbose version of code. Takes \\$ S \\$ as an inverted bitmask of length \\$ b \\$ and outputs \\$ n \\$ and \\$ k \\$ on separate lines. Explanation:

```
Ｗ¬№ωθ

```

Repeat until the desired bitmask is found in the current bitmask.

```
≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κω

```

Increment \\$ n \\$ and calculate the full bitmask for \\$ 1 \leq k + x \leq n + b \\$.

```
Ｉ⟦Ｌυ⌕ωθ

```

Output \\$ n \\$ and the index \\$ k \\$ of the input bitmask \\$ S \\$ in the full bitmask.

# Answer
> 3 votes
# K (ngn/k), ~~63~~ 54 bytes

```
{{(n+^k),k:*&(&/x=)'~(n(1+)\y)!''n:*z}[^y?x;x:1+!x]/1}

```

Try it online!

* `{{...}[^y?x;x:1+!x]/1}` set up a "converge" `/` starting with an `n` of `1`, fixing `y` as `1..b`, and `x` as a boolean mask indicating whether or not each value of `1..b` is present in `S` (`1`s if not present, `0`s if present). each invocation returns a pair of integers, `(n;k)`, with the execution ending when a valid `k` is identified
    + `n:*z` store the first value of `z` in `n`
    + `(n(1+)\y)` generate a (n+1)-by-b matrix; columns represent potential values of `x`, with rows representing potential values of `k`
    + `~(...)!''n` identify pairs where `k + x` divides `n`
    + `(&/x=)'` determine if each pair is invalid because `x` is in (or not in) `S`, then determine if all `x`s are valid for this `k`
    + `k:*&` identify the first valid `k` (if there isn't one, this returns `0N`, an integer null)
    + `(...),k` append the identified value of `k`...
    + `(n+^k)` to `n` if a valid `k` was identified, or an incremented `n` if not

# Answer
> 3 votes
# Brachylog, 27 bytes

```
∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧

```

Try it online!

### How it works

```
∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧
 .                          The output is
  Ċ                          [N, K], where …
   ℕᵐ                         N ≥ 0 and K ≥ 0, and …
     ≥₁                       N ≥ K.
       fʰ                   Factors of N
           z                 zipped with
         gᵗ                  K:
            ≜-ᵐ               label and take K from every factor.
               F            Save the result as F.
                &h⟦₁        [1, …, b]
                    ;Fx       without the elements in F
                       ~t?    is S.
                          ∧ Return output.

```

# Answer
> 2 votes
# Husk, ~~38~~ ~~33~~ ~~28~~ ~~22~~ 24 bytes

*Edits: -5 bytes thanks to Razetime, then -6 bytes thanks to Zgarb, then +2 bytes to fix bug that failed to find solutions for which `k` is zero*

```
§,o←ḟVImλVö=²`Wḣ⁴`%¹+ŀ)N

```

Try it online!

Arguments are integer `b` and list `S`; outputs pair of integers `(k,n)`.

My second Husk answer, and it took me *ages* to get it to work at all, so ~~I suspect it can still be golfed-down a lot~~ quite significantly golfed-down by Razetime & Zgarb...

Checks increasing values of `n`, and calculates the lowest `k` that can satisfy `S == (n%(b+k)>0)`. Then retrieves this value, and its index, as `k` and `n`, respectively.
*Edit:* In its original form, this missed solutions with `k` equal to zero, since this is the same result as failing to find a valid `k`. So now edited to calculate `k+1`, and then subtract 1 after retrieving the value.

***How?***

```
mλVö=²`Wḣ⁴`%¹+ḣ)N       # part 1: calculate first value of k+1 for each possible n
m                       # map function to each element of list
                N       # N = infinite list of natural numbers
 λVö=²`Wḣ⁴`%¹+ḣ)        # lambda function taking 1 argument:
  V           ŀ         # find the first 1-based index of k in 0..n with a truthy result of
   ö=²`Wḣ⁴`%¹+          # function to check if true indices of n%(k+b) are equal to S
   ö                    # composition of 4 functions
             +          # add b
          `%¹           # mod n
      `Wḣ⁴              # get set of truthy indices of 1..b
    =²                  # is this equal to S?
                        # (note that because we take the 1-based index
                        # of a range from 0..n, this part calculates k+1,
                        # or zero if there is no valid k)

§,o←ḟVI                 # part 2: return the first k, n
§                       # fork: apply func1 to the results of func2 & func3
 ,                      # func1 = join as pair
  o←ḟ                   # func2 (takes 2 args, 2-part fucntion combined using o):
                        #   increment the first truthy element of arg1 (a function) applied to arg2 (a list)
     V                  # func3 (takes 2 args): first truthy index of arg1 (a function) applied to arg2 (a list)
      I                 # arg1 for both func2 & func1 = identity function
                        # arg2 for both func2 & func1 is part1 above: the first k for each n (if any)

```

# Answer
> 1 votes
# Perl 5 `-p`, 70 bytes

```
/,/;++$k>$n?$k=0*++$n:0until"@{[grep$n%($k+$_),1..$`]}"eq$';$_="$n $k"

```

Try it online!

or less understandable and trickier 68 bytes

# `-lp`, 68 bytes

```
/,/;++$\>$,?$\=0*++$,:0until"@{[grep$,%($\+$_),1..$`]}"eq$';$_="$, "

```

Try it online!

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


title: Get the sequence steps

text:
# Question
Title: Get the sequence steps
**Challenge**

Given a sequence of numbers, create a function which returns the sequence steps.

* Assume a sequence will be `N >= 3`
* Sequence will repeat it steps at least once
* Sequence will only contain natural numbers
* Your function or program should return the shortest possible sequence of steps

**Example:**

Input: `[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]`

Output: `[1, 1, 2]`

**Explanation:** The initial sequence goes from `1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps)`. Then it repeats. The output then is `[1 step, 1 step, 2 steps] => [1, 1, 2]`

**Another example:**

Input: `[2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]`

Output: `[3, 1, 1, 1]`

```
[2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]
 \  /\ /\ /\ /
  3   1  1  1  Then it repeats...

```

**Test Cases**

`Input: [1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28] => Output: [3,4,1,1]`

`Input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] => Output: [5,2]`

`Input: [2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47] => Output: [4,4,3,4]`

`Input: [5, 6, 7] => Output: [1]`

---

**Clarifications**

* The input length - 1 is divisible by the output length
* Assume sequence will always going to be increasing

---

This is , so the shortest answer in bytes win.

# Answer
> 10 votes
# Jelly, ~~9~~ 7 bytes

```
IsJEƇḢḢ

```

Try it online!

### How it works

```
IsJEƇḢḢ  Main link. Argument: A (array)

I        Increment; compute D, the array of A's forward differences.
  J      Indices; yield [1, ..., len(A)].
 s       Split D into chunks of length k, for each k in [1, ..., len(A)].
   EƇ    Comb equal; keep only partitions of identical chunks.
     Ḣ   Head; extract the first matching parititon.
      Ḣ  Head; extract the first chunk.

```

# Answer
> 9 votes
# JavaScript (ES6), 58 bytes

Outputs a comma-separated string (with a leading comma).

```
a=>(a.map(p=x=>-(p-(p=x)))+'').match(/N((,\d+)*?)\1*$/)[1]

```

Try it online!

Or **56 bytes** if we use `,-` as the separator and we assume that the sequence is always *strictly* increasing.

### How?

We first convert the input array **a\[ \]** to a list of consecutive differences with:

```
a.map(p = x => -(p - (p = x)))

```

Because **p** is initially set to a non-numeric value (the callback function of *map()*), the first iteration yields *NaN*.

Example:

```
[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41]
[ NaN, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2 ]

```

We then coerce the result to a string:

```
"NaN,5,2,5,2,5,2,5,2,5,2"

```

Finally, we look for the shortest1 pattern of comma-separated integers (`,\d+`) starting right after "NaN" and repeating till the end of the string:

```
match(/N((,\d+)*?)\1*$/)

```

*1: using the non-greedy `*?`*

# Answer
> 6 votes
# Brachylog, 11 bytes

```
s₂ᶠ-ᵐṅᵐ~j₍t

```

Try it online!

Would be 5 bytes if there was a built-in for consecutive differences.

### Explanation

```
Example input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41]

s₂ᶠ             Find all substrings of length 2: [[6,11],[11,13],…,[34,39],[39,41]]
   -ᵐ           Map subtraction: [-5,-2,-5,-2,-5,-2,-5,-2,-5,-2]
     ṅᵐ         Map negate: [5,2,5,2,5,2,5,2,5,2]
       ~j₍      Anti-juxtapose the list of differences; the shortest repeated list is found
                  first, with the biggest number of repetitions: [5,[5,2]]
            t   Tail: [5,2]

```

# Answer
> 5 votes
# Japt, ~~14~~ 12 bytes

```
äa
¯@eUéX}aÄ

```

Try it

---

## Explanation

```
              :Implicit input of array U
äa            :Consecutive absolute differences
\n            :Reassign to U
 @    }aÄ     :Return the first positive integer X that returns true
   UéX        :  Rotate U right X times
  e           :  Check equality with U
¯             :Slice U to that element

```

---

## Original

```
äa
@eUîX}a@¯XÄ

```

Try it

# Answer
> 5 votes
# Pyth, 11 bytes

```
<J.+Qf.<IJT

```

Try it here

### Explanation

```
<J.+Qf.<IJT
 J.+Q          Call the sequence of differences in the input J.
     f         Find the first positive integer T...
      .<IJT    ... where rotating J by T doesn't change it.
<J             Take that many elements of J.

```

# Answer
> 5 votes
# , ~~49~~ 46 bytes

Full program:

```
d=diff(scan());while(any((s=d[1:T])-d))T=T+1;s

```

Try it online!

### , ~~72~~ ~~58~~ 54 bytes

Original function submission with all test cases in one place:

```
function(a,d=diff(a)){while(any((s=d[1:T])-d))T=T+1;s}

```

Try it online!

Thanks to JayCe for suggesting the full program route and -4 bytes on the function, and to Giuseppe for further -3.

# Answer
> 4 votes
# 05AB1E, 8 bytes

Saved 3 bytes thanks to Kevin Cruijssen.

```
¥.œʒË}нн

```

Try it online!

---

### 05AB1E, 11 bytes

```
āεI¥ô}ʒË}нн

```

Try it online!

```
āεI¥ô}ʒË}нн   Full program.
ā             Length range. Push [1 ... len(inp)].
 ε   }        For each...
  I¥ô         ... Chop the deltas into pieces of the corresponding size
      ʒË}     Keep only those that have all their elements equal.
         нн   And first retrieve the first element of the first one.

```

---

### 13 bytes

A cute alternative, IMO:

```
¥©ηʒDg®ôÙ˜Q}н

```

Try it online!

```
¥©ηʒDg®ôÙ˜Q}н   Full program.
¥               Push the deltas.
 ©              Copy them to the register.
  ηʒ       }    And filter the prefixes by...
    D     Q     ... Is the prefix itself equal to...
     g®ô        ... The deltas, split into chunks of its length...
        Ù˜      ... Deduplicated and flattened?
            н   Head.

```

# Answer
> 4 votes
# , 22 19 bytes

3 bytes saved thanks to FrownyFrog!

```
0{"1[:~./:|."{}.-}:

```

Try it online!

\[Try it online!\]\[TIO-ji2uiwla\]

## How?

```
                 -      find the successive differences by subtracting
                  }:    the list with last element dropped
               }.       from the list with the first element dropped
           |."{         rotate the list of differences
         /:             0..length-1 times (the input graded up)
     [:~.               remove duplicating rows
 0{"1                   take the first element of each row

```

# Answer
> 3 votes
# Javascript, 49 ~~56~~ bytes

*Edit* 7 bytes saved thanks (guess who?) Arnauld

Same regex idea as Arnauld, but curiously so different in implementation ...

Returning a string with steps comma separated (and a leading comma)

```
p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

```

**Test**

```
var F=
p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

;[[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]
,[1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28]
,[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41]
,[2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47]
,[5, 6, 7]]
.forEach(x=>console.log(x + ' -> ' + F(x)))
```

# Answer
> 3 votes
# MATL, ~~14~~ ~~13~~ 12 bytes

```
dt5YLFTF#Xu)

```

Try it online!

Just discovered that MATL does have a circulant function!

### Explanation

`d` \- Get the differences between successive terms, as an array

`t5YL` \- duplicate that, then call the `YL` ('gallery') function with `5` ('circulant') option. Creates a matrix with the given vector as first row, then successive rows are the same vector shifted circularly, until it wraps around.

`FTF#Xu` \- Check for unique rows and get their row numbers (not sure if there's a shorter way of doing this). When sequence steps repeat, the circularly shifted row will be the same as the first row, and the subsequent rows will be repeats. So this gets the indices of the first run of sequence steps before they start repeating.

`)` \- index using that into the original differences array, to get the answer.

---

Older:

```
d`tt@YS-a}@:)

```

Try it online!

*(-1 byte thanks to Giuseppe)*

### Explanation:

```
d   % Get the differences between successive terms, as an array
`   % Start do-while loop
  tt  % duplicate the difference array twice
  @   % push the current loop index value
  YS  % circularly shift the difference array by that amount
  -   % subtract the shifted diffs from the original diffs
  a   % see if the subtraction resulted in any non-zeros
    % if it did, shifted differences were not equal to original differences, so continue loop
}@ % if it didn't, then get loop index
:) % get the differences upto the loop index, before they started repeating
   % implicit loop end

```

# Answer
> 2 votes
# Java 10, ~~104~~ 100 bytes

```
a->{var t="";for(int i=a.length;i-->1;t+=a[i]-a[i-1]+" ");return t.replaceAll("( ?.+?)\\1*$","$1");}

```

Regex `( ?.+?)\1*$` for shortest repeating substring from *@Neil*'s comment on *@Arnauld*'s JavaScript (ES6) answer.

Try it online.

**Explanation:**

```
a->{                        // Method with integer-array parameter and String return-type
  var t="";                 //  Temp-String, starting empty
  for(int i=a.length;i-->1; //  Loop backward over the input-array, skipping the first item
    t+=a[i]-a[i-1]          //   Calculate the difference between two adjacent items
       +" ");               //   And append this with a space to the temp-String
  return t.replaceAll("( ?.+?)\\1*$",
                            //  Find the shortest repeating substring
                     "$1");}//  And only keep one such substring

```

# Answer
> 2 votes
# Ruby, 62 bytes

Relies on Regex logic adapted from Arnauld's answer.

```
->a{i=-2;a.map{|x|(i+=1)>=0?x-a[i]:0}*?,=~/((,\d+)*?)\1*$/;$1}

```

Try it online!

Alternative determination of step differences, also 62 bytes:

```
->a{[0,*a.each_cons(2).map{|x,y|y-x}]*?,=~/((,\d+)*?)\1*$/;$1}

```

Try it online!

# Answer
> 2 votes
# Python 2, 101 bytes

```
def f(l):d=[y-x for x,y in zip(l,l[1:])];g=len(l);print[d[:k]for k in range(1,g+1)if g/k*d[:k]==d][0]

```

Try it online!

First generates the deltas **d**, then finds the first prefix **p** of **d** that when repeated **⌊len(L) / len(p)⌋** times yields **L**, where **L** is the input list.

# Answer
> 1 votes
# APL+WIN, 39 bytes

Prompt for input.

```
(↑((⍴v)=+/¨(⊂v)=(⍳⍴v)⌽¨⊂v)/⍳⍴v)↑v←-2-/⎕

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
v←-2-/⎕ Prompt for input and take successive differences

(⍳⍴v)⌽¨⊂v create a nested vector ans sequentially rotate by one to length of v

+/¨(⊂v)= compare to original v and sum positions where there is match

(⍴v)= identify where all elements match

(↑(....) identify number of rotations giving a first complete match

(↑(...)↑v take first number of elements from above from v as repeated sequence

```

# Answer
> 1 votes
# Python 2, ~~86~~ 85 bytes

```
def f(a,n=1):d=[y-x for x,y in zip(a,a[1:])];return d[:-n]==d[n:]and d[:n]or f(a,n+1)

```

Try it online!

Construct the differences as `d`; if `d` repeats with unit size `n` then `d[n:]==d[:-n]`; else recurse.

# Answer
> 1 votes
# Stax, ~~8~~ 6 bytes

```
░»F\☺»

```

Run and debug it

Here's an unpacked annotated version to show how it works.

```
:-  pairwise differences
:(  all leftward rotations of array
u   keep only unique rotations
mh  output the first element from each unique rotation

```

Run this one

# Answer
> 1 votes
# Retina 0.8.2, 42 bytes

```
\d+
$*
(?<=(1+),)\1

1+(.+?)\1*$
$1
1+
$.&

```

Try it online! Link includes test cases. Output includes leading comma. Explanation:

```
\d+
$*

```

Convert to unary.

```
(?<=(1+),)\1

```

Compute forward differences, except for the first number, which gets left behind.

```
1+(.+?)\1*$
$1

```

Match repeating differences.

```
1+
$.&

```

Convert to decimal.

# Answer
> 1 votes
# 05AB1E, ~~14~~ 13 bytes

```
¥DηvÐNƒÁ}QD—#

```

Try it online or verify all test cases.

I know there are already two shorter 05AB1E answers posted by *@Mr.Xcoder*, but I wanted to try this alternative approach using rotation and equality check.
Might be able to golf it down a few bytes without dropping `Á`.

-1 byte after a tip of *@Emigna* to remove the global\_variable registers (`©` and 2x `®`) and use a Duplicate (`D`) and a Triplicate (`Ð`) instead.

**Explanation:**

```
¥             # Calculate the deltas of the input-array
              #  i.e. [1,2,3,5,6,7,9] → [1,1,2,1,1,2]
 D            # Duplicate it
  η           # Push all its prefixes
              #  [1,1,2,1,1,2] → [[1],[1,1],[1,1,2],[1,1,2,1],[1,1,2,1,1],[1,1,2,1,1,2]]
v             # For-each over these prefixes
 Ð            #  Triplicate the (duplicated) deltas-list
  NƒÁ}        #  Rotate the deltas-list N+1 amount of times,
              #  where N is the prefix index (== prefix_length-1)
              #   i.e. [1,1,2] and [1,1,2,1,1,2] (rotate 3 times) → [1,1,2,1,1,2]
      Q       #  If the rotated deltas and initial deltas are equal
              #   [1,1,2,1,1,2] and [1,1,2,1,1,2] → 1
       D—#    #  Print the current prefix-list, and stop the for-each loop

```

# Answer
> 1 votes
Haskell, 107 bytes

```
let i=map(uncurry(-))$zip(tail x)(init x)in head$filter(\s->take(length i)(concat$repeat s)==i)(tail$inits i)

```

x is the input array.

# Answer
> 1 votes
# Perl 6, 57 bytes

```
{~(.rotor(2=>-1).map:{.[1]-.[0]})~~/^(.+?){}" $0"+$/;~$0}

```

Test it

Output is space separated (`"1 1 2"`)

## Expanded:

```
{      # bare block lambda with implicit parameter $_

  ~(   # stringify (space separated)

    .rotor( 2 => -1 )     # from the input take 2 backup 1, repeat
    .map: { .[1] - .[0] } # subtract each pair to find the differences
  )

  ~~   # smartmatch

  /    # regex

    ^  # beginning of string

    ( .+? ) # match at least one character, but as few as possible
    {}      # make sure $0 is set (probably a compiler bug)
    " $0"+  # match $0 one or more times (with a leading space)

    $  # end of string
  /;

  ~$0  # return the stringified $0
}

```

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
¥©η.ΔÞ®Å?

```

Explanation:

```
          # take input implicitly
¥         # deltas, eg [4, 5, 7, 8, 10] -> [1, 2, 1, 2]
 ©        # save this to the global register
  η       # prefixes, eg [1, 2, 1, 2] -> [[1], [1, 2], ...]
   .Δ     # find the first one such that
     Þ    # cycled infinitely, eg [1, 2] -> [1, 2, 1, 2, ...]
       Å? # starts with
      ®   # the global register
          # and implicitly print the found element

```

Alternative 9-byte:

```
¥η.ΔÞ.¥-Ë

```

Same algo, but instead of comparing to the list of deltas (which needs to be saved/restored), this uses  (undelta) then compares to the (implicit) input.

Try it online!

# Answer
> 1 votes
# Perl 5 `-p`, 55 bytes

```
s/\d+ (?=(\d+))/($1-$&).$"/ge;s/\d+$//;s/^(.+?)\1*$/$1/

```

Try it online!

Numbers are input as a space separated list. Output is the same format.

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~26~~ 23 bytes

```
FindRepeat@*Differences

```

Try it online!

# Answer
> 1 votes
# Husk, 12 bytes

```
←ḟΛ=Um`CẊ≠⁰N

```

Try it online! or Verify all test cases

# Answer
> 0 votes
# K4, 30 bytes

**Solution:**

```
(*&d~/:c#'(!c:#d)#\:d)#d:1_-':

```

**Examples:**

```
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20
3 1 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17
1 1 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28
3 4 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41
5 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47
4 4 3 4
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':5 6 7
,1

```

**Explanation:**

Seems hefty for what we're trying to solve. Get the deltas of the input and then build sequences and determine the shortest one that matches it.

```
(*&d~/:c#'(!c:#d)#\:d)#d:1_-': / the solution
                           -': / deltas
                         1_    / drop first
                       d:      / save as d
                      #        / take (#) from
(                    )         / do this together
                 #\:d          / take (#) each-left (\:) from d
          (     )              / do this together
              #d               / count length of d
            c:                 / save as c
           !                   / range 0..c-1
       c#'                     / take c copies of each
   d~/:                        / d equal (~) to each right (/:)
  &                            / where true
 *                             / first one

```

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


title: Find the super palindromes!

text:
# Question
Title: Find the super palindromes!
> Consider the number 99999999. That number is obviously a palindrome. The largest prime factor of 99999999 is 137. If you divide 99999999 by 137, you get 729927. This number is also a palindrome.
>
> The largest prime factor of 729927 is 101. 729927/101=7227 which again is a palindrome.
>
> The largest prime factor of 7227 is 73. 7227/73=99 which again is a palindrome.
>
> By further dividing by the largest prime factor, you get 9, 3 and finally 1, which, being one-digit numbers, are also palindromes. Since 1 has no prime factors, the procedure ends here.
>
> Now generalizing this observation, I define a super-palindrome as a palindrome which is either 1, or which gives another super-palindrome if divided by its largest prime factor.

Credits: https://math.stackexchange.com/questions/200835/are-there-infinitely-many-super-palindromes

Given a number *N*, determine if it is a super palindrome or not, and print a truthy or falsey value accordingly.

Your program should print a truthy value for these inputs:

```
1
101
121
282
313
353
373
393
474
737
919
959
1331
1441
2882
6446
7887
8668
9559
9779

```

Your program should print a falsey value for these inputs:

```
323
432
555
583
585
646
642
696
777
969
989
2112
3553
4554
5242
5225
5445
8080
8118
9988

```

Remember, this is , so the code with the shortest amount of bytes wins.

# Answer
> 8 votes
# Jelly, ~~13~~ ~~12~~ ~~9~~ 8 bytes

```
Æf×\D⁼U$

```

Try it online! or verify all test cases.

### How it works

```
Æf×\D⁼U$  Main link. Argument: n

Æf        Yield all prime factors of n, with multiplicities and in ascending order.
  ×\      Take the cumulative product.
    D     Decimal; convert each product into the array of its base 10 digits.
       $  Combine the two links to the left into a monadic chain.
      U     Upend; reverse all arrays of decimal digits.
     ⁼      Test for equality.

```

# Answer
> 6 votes
# Mathematica, 64 bytes

```
And@@PalindromeQ/@FixedPointList[#/FactorInteger[#][[-1,1]]&,#]&

```

Unnamed function, returning `True` or `False`. Forms a list by starting at the input, then iterating the function "me divided by my largest prime factor" until the output doesn't change. (Fortunately, Mathematica now thinks the largest prime factor of 1 is 1.) Then tests whether the list entries are palindromes (yay built-ins! boo function name length!) and `And`s them all together.

# Answer
> 6 votes
# Mathematica, 51 bytes

```
#<2||PalindromeQ@#&&#0[#/FactorInteger[#][[-1,1]]]&

```

Recursive anonymous function. Takes a number as input and returns `True` or `False` as output.

# Answer
> 6 votes
# 05AB1E, ~~9~~ 8 bytes

Saved a byte thanks to *Adnan*.

```
Ò.pPDíïQ

```

Try it online!

**Explanation**

`n = 7227` used as example

```
Ò           # prime factors with duplicates
            # STACK: [3, 3, 11, 73]
 .p         # prefixes
            # STACK: [[3], [3, 3], [3, 3, 11], [3, 3, 11, 73]]
   P        # product
            # STACK: [3, 9, 99, 7227]
    D       # duplicate
            # STACK: [3, 9, 99, 7227], [3, 9, 99, 7227]
     í      # reverse each
            # STACK: [3, 9, 99, 7227], ['3', '9', '99', '7227']
      ï     # convert to  int
            # STACK: [3, 9, 99, 7227], [3, 9, 99, 7227]
       Q    # check for equality
            # STACK: 1
            # implicit output

```

# Answer
> 5 votes
# Pyth - ~~15~~ 12 bytes

~~Beat Jelly :P~~ :/

Unfortunately, all those implicit maps do not get shorter when combined into an explicit one since the last one is an auto-splat.

```
.A_IM`M*M._P

```

Test Suite.

Gets all the prefixes of the prime factorization, the products of which will be the intermediate super palindromes, and checks if all of them are palindromes.

# Answer
> 4 votes
# Mathematica, ~~71~~ 63 bytes

```
And@@PalindromeQ/@FoldList[1##&,Join@@Table@@@FactorInteger@#]&

```

# Explanation

```
FactorInteger@#

```

Factor the input. (e.g. `8668 -> {{2, 2}, {11, 1}, {197, 1}}`; for each list in the output, the first element is the prime factor, and the second one is the power.

```
Join@@Table@@ ...

```

For each factor-power pair, duplicate the first element by the second element, and flatten the entire thing. (`{{2, 2}, {11, 1}, {197, 1}} -> {{2, 2}, {11}, {197}} -> {2, 2, 11, 197}`)

```
FoldList[1##&, ... ]

```

Iterate through the list, multiplying the elements. (`{2, 2, 11, 197} -> {2, 2 * 2, 2 * 2 * 11, 2 * 2 * 11 * 197} -> {2, 4, 44, 8668}`)

```
And@@PalindromeQ/@ ...

```

Check whether all of the resulting numbers are palindromes, and apply the `And` operator. (`{2, 4, 44, 8668} -> {True, True, True, True}` -\> `True`)

# Answer
> 3 votes
# Brachylog, 14 bytes

```
1|r?$ph:?r/:0&

```

Try it online!

### Explanation

This implements the formula explained in the challenge description.

Computing all products of suffixes of the prime factorization and checking that they are all palindromes is 1 byte longer (`1|$p:@]f:{*.r}a`).

```
1                  Input = 1
 |                 OR
  r?               Reversing the Input results in the Input
    $p             Get the prime factors of the Input
      h            Take the first one (the biggest)
       :?r/        Divide the Input by that prime factor
           :0&     Call this predicate recursively with that new number as input

```

# Answer
> 2 votes
## Racket 238 bytes

```
(define(p n)(=(string->number(list->string(reverse(string->list(number->string n)))))n))
(if(= n 1)#t(begin(let o((n n))(define pd(prime-divisors n))(if(null? pd)#f(begin(let((m(/ n(last pd))))
(cond[(= m 1)#t][(p m)(o m)][else #f])))))))

```

Ungolfed:

```
(define (f n)
  (define (palin? n)                      ; define palindrome of number
    (=(string->number
       (list->string
        (reverse
         (string->list
          (number->string n)))))
      n))
  (if(= n 1)#t
     (begin
       (let loop ((n n))
         (define pd (prime-divisors n))   ; find prime divisors
         (if (null? pd) #f                ; end if none- not superpalindrome
             (begin
               (let ((m (/ n (last pd)))) ; divide by largest prime divisor
                 (cond                    ; test quotient
                   [(= m 1) #t]           ; end if 1: super-palindrome found
                   [(palin? m) (loop m)]  ; loop with quotient if palindrome
                   [else #f]              ; end if not palindrome
                   ))))))))

```

Testing:

```
(f 1)
(f 101)
(f 121)
(f 282)
(f 313)
(f 353)
(f 373)
(f 393)
(f 474)
(f 737)
(f 919)
(f 959)
(f 1331)
(f 1441)
(f 2882)
(f 6446)
(f 7887)
(f 8668)
(f 9559)
(f 9779)
(f 99999999)

```

Output:

```
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t

```

# Answer
> 2 votes
# J, 30 bytes

```
0:`(%1>.{:@q:)@.((-:|.)@":)^:_

```

Error for falsey, 1 for truthy.

Initial attempt, does not error for falsey, 40 bytes:

```
0:`(([:$:]%{:@q:)`[@.(1&=))@.((-:|.)@":)

```

## Explanation

```
0:`(%1>.{:@q:)@.((-:|.)@":)^:_
                           ^:_  repeat until convergent
              @.((-:|.)@":)     if the number is palindromic:
   (         )                   do the stuff inside, which is a 4-train
        {:@q:                    largest prime factor
     1>.                         (or 1, if smaller than 1)
    %                            divide the original number by this value
0:`                             otherwise, return 0
                                (because of ^:_, this will be passed into q:, which will
                                error because 0 cannot be factored.)

```

## Test cases

```
   NB. collect errors; 0 if errored, otherwise the result of the function
   NB. left arg: values; right arg: boxed name of function
   errors =: 4 : 0
    f =. y`:6
    l =: ''
    for_e. x do.
        try.
            l =. l , f e
        catch.
            l =. l , 0
        end.
    end.
    l
)
   s =: 0:`(%1>.{:@q:)@.((-:|.)@":)^:_
   t =: 1 101 121 282 313 353 373 393 474 737 919 959 1331 1441 2882 6446 7887 8668 9559 9779
   f =: 323 432 555 583 585 646 642 696 777 969 989 2112 3553 4554 5242 5225 5445 8080 8118 9988
   t ,. f
   1  323
 101  432
 121  555
 282  583
 313  585
 353  646
 373  642
 393  696
 474  777
 737  969
 919  989
 959 2112
1331 3553
1441 4554
2882 5242
6446 5225
7887 5445
8668 8080
9559 8118
9779 9988
   (t ,. f) errors"1 0 <'s'
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0

```

# Answer
> 2 votes
# 아희(Aheui), 309 bytes (100 chars * 3 bytes + 9 newlines)

```
방빩반룸있쁏멐솔쌀잌
앟놂숙참뿔썁썸뻙솝셜
본서번분번뮴딸냥별쀼
슉눇번낢퉅쑫썬쌀본묳
뽇서본석첫삭뽑롷떵춤
분촐럶사눙읽숟뗘분뻨
듐삭빶쏘윙잉썩손뵬괆
쌰뭉쇼텰궮변번첳웅텩
뽇흶아희쾯볻훼윺엄솝
코드골프욉쁍숙쌉삼쏩

```

I'm so happy that I actually finished it!

I'm new to this language, so any tip on improving byte count is welcome.

Try it here! (copy and paste the code)

**Cleaner version**

```
방빠반루ㅇ쀼머솔쌀이
아노숙차뿌썁썸뻐솝셜
본서번분번뮤따냐별쀼
슉누번나투쑫썬쌀본묘
뽀서본석처삭뽀로떠추
분초러사누이숟뗘분뻐
듀삭빠쏘ㅇ이썩손뵬ㅇ
쌰뭉쇼텨이변번처우텨
뽀희ㅇㅇㅇ볻ㅇ유어솝
ㅇㅇㅇㅇㅇㅇ숙쌉삼쏩

```

# Answer
> 1 votes
# Husk, ~~9~~ 7 bytes

```
ΛS=↔G*p

```

Try it online!

-2 bytes from Jo King.

# Answer
> 0 votes
# Actually, 29 bytes

There are probably several sections of this code that could be golfed, though I'm not sure where yet. Golfing suggestions welcome. Try it online!

```
╗1`X╜$;R=;╝╜yN╜\;╗1<&`╬X╜DY╛&

```

**Ungolfing**

```
          Implicit input n.
╗         Save n to register 0.
1`...`╬   Run the following function on the stack while TOS is truthy.
  X         Discard the previous truthy.
  ╜         Push n from register 0.
  $         Push str(n).
  ;R=       Check if str(n) == str(n)[::-1], i.e. if n is a palindrome.
  ;╝        Save a copy of (is n a palindrome?) to register 1.
  ╜yN       Get the largest prime factor of n.
  ╜\        Divide n by its largest prime factor.
  ;╗        Save a copy of n // l_p_f to register 0.
  1<        Check if 1 < n // l_p_f. This returns 0 only if n // l_p_f is 1.
  &         Logical AND (is n a palindrome?) and (is n // l_p_f > 1?).
            This quits if we have reached a non-palindrome or we have reached 1.
X         Discard the falsey that ended the previous function.
╜         Get the last value saved to register 0 (could be 1 or a non-palindrome // l_p_f)
DY        This returns 1 if register 0 was a 1, else 0.
╛&        Logical AND with register 1 (was the last n a palindrome?) to get our result.
          Implicit return.

```

# Answer
> 0 votes
# Scala, 138 bytes

```
def?(n:Int):Int={val p=Stream.from(2).filter(n%_==0)(0)
if(p==n)n else?(n/p)}
def s(i:Int):Boolean=i<2||(i+"")==(i+"").reverse&&s(i/ ?(i))

```

Ungolfed:

```
def largestFactor(n:Int):Int={
  val p=Stream.from(2).filter(n%_==0).head
  if(p==n)n else largestFactor(n/p)}
def superPalindrome(i:Int):Boolean=i<2||(i+"")==(i+"").reverse&&superPalindrome(i/ largestFactor(i))

```

Explanation:

```
def?(n:Int):Int={                       //define a method for the largest prime factor
  val p=Stream.from(2).filter(n%_==0)(0)  //find the first factor of n
  if(p==n)n else?(n/p)                    //if it's n, return n else the next factor
}
def s(i:Int):Boolean=                     //method for the superprime
  i<2                                     //if s<2 return true
  ||                                      //else return:
    (i+"")==(i+"").reverse                  //is i a palindrome
    &&                                      //and
    s(i/ ?(i))                              //is i divided by it's largestPrimeFactor a superpalindrome

```

# Answer
> 0 votes
## JavaScript (ES6), 78 bytes

```
(n,d=2,p=1)=>n%d?n<2||f(n,d+1,p):[...p=p*d+''].reverse().join``==p&&f(n/d,d,p)

```

Recursively builds the prime factorisation prefixes and checks them for palindromicity.

# Answer
> 0 votes
# Java 7, 133 bytes

```
int c(int a){int x=a,y=0,z=a,i=2;for(;x>0;y=y*10+x%10,x/=10);for(;z>1;i++)for(;z%i<1;z/=i);if(a<2)return 1;return y!=a?0:c(a/(i-1));}

```

# Ungolfed

```
    static int c( int a ){
    int x = a , y = 0 , z = a , i = 2 ;

    for ( ; x > 0 ; y = y * 10 + x % 10 , x /= 10 ) ;

    for ( ; z > 1 ; i++ )
    for ( ; z % i < 1 ; z /= i ) ;

    if ( a < 2 )
      return 1 ;

    return y != a ? 0 : c( a / ( i - 1 ) ) ;
 }

```

---
Tags: code-golf, number, palindrome
---


title: Fully-palindromic triangles

text:
# Question
Title: Fully-palindromic triangles
Consider the string `160615051`. It can be "triangulated" as such:

```
  1
 606
15051

```

Then, each row is a palindrome. Also note that each side on the perimeter is also a palindrome:

```
  1  |   1   |
 6   |    6  |
1    |     1 | 15051

```

Therefore, this string can be considered to be a fully-palindromic triangle. Don't worry about the altitude `100` in this case, it doesn't have to be palindromic.

**Input:** A string of printable ASCII characters from 0x20 to 0x7E. This can be a character array, a single string, or an array of ASCII code points. Your input will always be able to be triangulated (that is, its length will always be a perfect square).

**Output**: A truthy value if the string is a fully-palindromic triangle, or a falsey value otherwise.

## Test cases

```
input => output

1 => true
A => true
AAAA => true
nope => false
{{}} => false
1101 => true
1011 => false
1202 => false
111110001 => true
160615051 => true
160625052 => false
1111111111111111 => true
1121123211234321123454321 => true
HHeHHeleHHellleHHellolleH => true
HellolleHHellleHHeleHHeHH => false
111111111111111111111111111111111111 => true
abcbdefeddefgfedbcdefedcbabcdefedcba => true

```

# Answer
# Jelly, ~~14~~ 12 bytes

```
J’Æ²œṗZ⁻¦µU⁼

```

Try it online!

### Background

We start by looking at the 0-based indices of the input string.

```
 H  H  e  H  H  e  l  e  H  H  e  l  l  l  e  H  H  e  l  l  o  l  l  e  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

```

To get the rows of the triangle, we can split the string before the indices **1**, **1 + 3 = 4**, **1 + 3 + 5 = 9**, and **1 + 3 + 5 + 7 = 16**. Since **(n + 1)² = n² + (2n + 1)**, these sums are precisely the positive, perfect squares in the index list. If we also split the string before **0**, this is as simple as splitting before all 0-based indices that are perfect squares.

After splitting, we get the following strings.

```
""
"H"
"HeH"
"HeleH"
"HellleH"
"HellolleH"

```

Next, we replace the empty string at the beginning with all the characters in the first column.

```
"HHHHH"
"H"
"HeH"
"HeleH"
"HellleH"
"HellolleH"

```

The task is now reduced to checking whether reversing all strings yields the same string array.

### How it works

First `J` generates all 1-based indices of the input string `J`, then decrements them with  to yield all 0-based indices. `Æ²` tests all 0-based indices for squareness. For our example from above, this yields the following Boolean array.

```
 1  1  0  0  1  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0

```

Next, we call `œṗ` to partition the input string, e.g.,

```
 H  H  e  H  H  e  l  e  H  H  e  l  l  l  e  H  H  e  l  l  o  l  l  e  H

```

before all **1**'s (actually, all truthy elements). For our example, this yields the following string array.

```
['',
 'H',
 'HeH',
 'HeleH',
 'HellleH',
 'HellolleH'
]

```

`Z⁻¦` is arguably the most interesting part of this answer. Let's analyze the more straightforward `Z1¦` first.

`¦` is the *sparse* quick. It consumes two links from the stack, specifically `1` and `Z` in this case. First `Z` is applied to its argument: the string array from before. `Z` is the *zip* atom and reads the string array / 2D character array by columns, yielding

```
['HHHHH',
 'eeee',
 'Hlll',
 'ell',
 'Hlo',
 'el',
 'Hl',
 'e',
 'H'
]

```

What used to be left side of the input string and the first column of the string array now becomes the first *string*.

Now `¦` peeks at `1` and finds a single index: **1**. Thus the first string in the original string array is replaced with the first string in the return value of `Z`; strings at other indices remain unaffected.

```
['HHHHH',
 'H',
 'HeH',
 'HeleH',
 'HellleH',
 'HellolleH'
]

```

Let's call this array **A**.

We used `Z⁻¦` instead of `Z1¦`, but this makes no difference:  compares the string array with the input string for inequality, yielding **1** since they're not equal. The difference between the two is that `Z⁻¦` is dyadic because  is, allowing us to write `œṗZ⁻¦` instead of `œṗ¹Z1¦`. This is because a dyad (`œṗ`) followed by a monad (`œṗ¹Z1¦`) is a *fork* (the monad is applied to the chain's argument / the input string, and the returned value is passed as the right argument to `œṗ`), while a dyad followed by another dyad (or at the end of the chain) is a *hook*, i.e., its right argument is the chain's argument.

All that's left to do is check for palindromicness. `µ` begins a new (monadic) chain who's argument is **A**. The *upend* atom `U` reverses all strings in **A** (but not **A** itself), then  compares the result with **A** for equality. The returned Boolean **1** indicates a fully-palindromic triangle; other strings would return **0**.
> 10 votes

# Answer
# Japt, ~~25~~ ~~21~~ 17 bytes

*Saved 2 bytes thanks to @obarakon*

```
ò@°T ¬v1
pUmg)eêP

```

Test it online!

### How it works

```
 ò@  ° T ¬ v1   // Implicit: U = input string, T = 0
UòXY{++T q v1}  // First line; reset U to the result of this line.
UòXY{        }  // Partition U at indices where
     ++T q      //   the square root of T incremented
           v1   //   is divisible by 1.
                // This breaks U at square indices, giving rows of 1, 3, 5, ... chars.
 pUmg)eêP
UpUmg)eêP
  Umg           // Take the first char of every item of U.
Up   )          // Append this to U.
      e         // Check that every item in the resulting array
       êP       // is a palindrome.
                // Implicit: output result of last expression

```

Note that we don't need to check *both* sides; if the sides are not the same, At least one of the rows is not a palindrome.
> 6 votes

# Answer
# 05AB1E, 18 bytes

```
gÅÉ£õÜÐíQs€¬āÈÏÂQ*

```

Uses the **05AB1E** encoding. Try it online!
> 4 votes

# Answer
# Jelly, ~~18~~ 16 bytes

```
J²‘Ṭœṗ⁸ZḢ$ṭ$ŒḂ€Ạ

```

Try it online!

Thanks to Jonathan Allan for trivial but not so obvious -2 byte savings.
> 4 votes

# Answer
## JavaScript (ES6), 112 bytes

```
f=(s,n=1,t='',u='',g=([...a])=>''+a==a.reverse())=>s?g(s.slice(0,n))&f(s.slice(n),n+2,t+s[0],u+s[n-1]):g(t)&g(u)

```

`t` and `u` collect the sides so that they can be tested at the end.
> 3 votes

# Answer
# C#, 184 bytes

```
using System.Linq;
b=a=>string.Concat(a.Reverse())==a
f=>{string c=f[0]+"",d=c,e="";for(int i=1,k=1,s=f.Length;i<s;)
{c+=f[i];d+=f[(i+=k+=2)-1];e=f.Substring(s-k);}return b(c)&b(d)&b(e);}

```

Thought the solution was looking good until I got to the palindrome part

Ungolfed version:

```
Func<string, bool> b = a => string.Concat(a.Reverse()) == a;
        Func<string, bool> func = f => {

            string c = f[0] + "", d = c, e = "";

            for (int i = 1, k = 1, s = f.Length; i < s;) {
                c += f[i];
                d += f[(i += k += 2) - 1];
                e = f.Substring(s - k);
            }

            return b(c) & b(d) & b(e);
        };

```
> 2 votes

# Answer
# Java 8, ~~358~~ 301 bytes

```
import java.util.*;s->{List<String>l=new Stack();for(int i=0,p=1,t=1;p<=s.length();p+=t+=2)l.add(s.substring(i,i=p));String a="",b=a;for(String q:l){a+=q.charAt(0);b+=q.charAt(q.length()-1);}return p(a)&p(b)&p(l.get(l.size()-1));}boolean p(String s){return s.equals(new StringBuffer(s).reverse()+"");}

```

Input is a `String`, output is a `boolean`.

**Explanation:**

Try it here.

```
import java.util.*;               // Required import for List and Stack

s->{                              // Method (1) with String parameter and boolean return-type
  List<String>l=new Stack();      //  Create a String-list
  for(int i=0,p=1,t=1;            //  Initialize some index/counter integers
      p<=s.length();              //  Loop (1) over the String in sections
      p+=t+=2)                    //    And increase `p` like this after every iteration: 1,4,9,16,25,etc.
    l.add(s.substring(i,i=p));    //   And add a substring-section to the list (0,1 -> 1,4 -> 4,9 -> 9,16 -> etc.)
                                  //  End of loop (1) (implicit / single-line body)
  String a="",b=a;                //  Two temp Strings
  for(String q:l){                //  Loop (2) over the list
    a+=q.charAt(0);               //   And append the first character to String `a`
    b+=q.charAt(q.length()-1);    //   And the last character to String `b`
  }                               //  End of loop (2)
  return p(a)                     //  Return if String `a` is a palindrome
        &p(b)                     //   as well as String `b`
        &p(l.get(l.size()-1));    //   as well as the last String in the list
}                                 // End of method (1)

boolean p(String s){              // Method (2) with String parameter and boolean return-type
  return s.equals(new StringBuffer(s).reverse()+"");
                                  //  Return if this String is a palindrome
}                                 // End of method (2)

```
> 2 votes

# Answer
# Jelly,  ~~20~~  21 bytes

+2 bytes - I released buggy code :(
-1 byte - moved from moulding like odd integers to partitioning at square indexes

```
JÆ²0;œṗ⁸ZḢ$ṭ$ŒḂ€Ạ

```

A monadic link accepting a list of characters and returning `1` (Truthy) or `0` (Falsey).
Note: this uses the part of the specification that limits the input to a square length.

**Try it online!** or see the test suite.

This may be simplified to **17 bytes** by noting that if all rows are palindromes only one "side" needs checking (`JÆ²0;œṗ⁸ZḢ$ṭ$ŒḂ€Ạ`), however Erik the Outgolfer already noticed this fact and used it in their answer so I have given the triangle construction method to them saving a byte there.

Additionally, that may in turn be improved to **16 bytes** by noting that partitioning at truthy indexes does not mind if there is excess in the left argument (`J²‘Ṭœṗ⁸ZḢ$ṭ$ŒḂ€Ạ`).

### How?

```
JÆ²0;œṗµ2BịÐ€⁸Z;⁸ŒḂ€Ạ - Link: list, a      e.g. "abcbazxza"
J                     - range of length of a  = [1,2,3,4,5,6,7,8,9]
 Æ²                   - is square? (vectorises) [1,0,0,1,0,0,0,0,1]
   0;                 - prepend a zero        [0,1,0,0,1,0,0,0,0,1]
     œṗ               - partition a at 1s     ["a","bcb","azxza"]
       µ              - monadic chain separation, call that t
        2B            - 2 in binary = [1,0]
             ⁸        - chain's left argument, t
          ịÐ€         - map with index into    ["aa","bb","aa"] (1st and last of each of t)
              Z       - transpose              ["aba","aba"] (left and right "sides" of t)
               ;⁸     - concatenate t          ["aba","aba","a","bcb","azxza"]
                 ŒḂ€  - palindromic? for €ach  [1,1,1,1,1]
                    Ạ - all?                   1

```
> 1 votes

# Answer
# PHP, 97 bytes

```
for($t=1;~$s=substr($argn,$i**2,$i++*2+1);$d.=$s[0])$t&=strrev($s)==$s;$t&=strrev($d)==$d;echo$t;

```

Try it online!
> 1 votes

# Answer
# Mathematica, 156 bytes

```
B=StringTake;Count[PalindromeQ/@Join[A=Table[B[#,{i^2+1,(i+1)^2}],{i,0,(s=Sqrt@StringLength@#)-1}],{StringJoin@Table[B[A[[i]],1],{i,Length@A}]}],True]==s+1&

```

**input**

> \["1101"\]
> 1 votes

# Answer
# Java, 136 bytes

```
l->{for(int i=0,j,k=1;i<l.size();i=j,k+=2)if(!l.subList(i,j=i+k).equals(l.subList(i,j).asReversed().toList()))return false;return true;}

```

Uses a `MutableList<Character>` from Eclipse collections

```
Function<MutableList<Character>, Boolean> func = l->{
   for(int i=0,j,k=1;i<l.size();i=j,k+=2)  // `i` is the start index, `j` is the end index, `k` increments by 2
       if(!l.subList(i,j=i+k).equals( //Check that the first partition equals
           l.subList(i,j).asReversed().toList())  // The same sublist reversed
       )
       return false;
   return true;
};

```
> 1 votes

# Answer
# Perl 5, 81 + 1 (`-p`) = 82 bytes

```
$a[0].=$1while($a[++$q]=substr$_,0,($#i+=2),'')=~/(.)/;$\||=$_ ne reverse for@a}{

```

Try it online!

Outputs `undef` (i.e., blank, null) for true, any number for false
> 1 votes

# Answer
# Python 2, ~~128~~ ~~118~~ 115 bytes

```
def f(s):
 w=1;l=r='';b=[]
 while s:l+=s[0];r+=s[w-1];b+=[s[:w]];s=s[w:];w+=2
 print all(d==d[::-1]for d in[l,r]+b)

```

Try it online!
> 0 votes

# Answer
# Excel VBA, 87 Bytes

Anonymous VBE immediate window function that takes input from cell `[A1]` and outputs to the VBE immediate window

```
k=1:For i=1To[Len(A1)^.5]:s=Mid([A1],j+1,i*2-1):j=j+i*2-1:k=k*(s=StrReverse(s)):Next:?k

```
> 0 votes

# Answer
# APL (Dyalog Extended), 38 bytes

```
{(⌽¨≡⊢)(⊢,⊢/¨,⍥⊂⊃¨)⍵⊆⍨w⍴∊⍴⍨¨1+2×⍳w←≢⍵}

```

Try it online!

The cuts are of size `1,3,5,7...`, so that is used with  to get the appropriate array.

Requires `⎕IO←0` for zero indexing.

Shortened with a lot of help from Marshall and dzaima.

## Explanation

```
{(⌽¨≡⊢)(⊢,⊢/¨,⍥⊂⊃¨)⍵⊆⍨w⍴∊⍴⍨¨1+2×⍳w←≢⍵}
                                   ≢⍵  length of the string
                                 w←    assign to var w
                                ⍳      range from 0..length-1
                            1+2×       convert each to 2n+1 (odd numbers)
                         ⍴⍨¨           replicate each element times itself
                        ∊              flatten that
                      w⍴               reshape to string's length
                   ⍵⊆⍨                 partition the string based on that
       (⊢,⊢/¨,⍥⊂⊃¨)                    Train:
       (⊢,        )                    concatenate the partition with:
       (  ⊢/¨     )                    last character of each partition
       (        ⊃¨)                    first character of each partition
       (      ⍥⊂  )                    both enclosed into two strings
  ⌽¨                                   do the reverses of each part
    ≡                                  match
     ⊢                                 the parts?

```
> 0 votes

---
Tags: code-golf, string, palindrome
---