title: Let's study Neil numbers

text:
# Question
Title: Let's study Neil numbers
Congratulations to Neil for hitting 100k rep! As a tribute, we are going to study 'Neil numbers'.

Neil's user ID is **17602** and there's something special about the binary representation of this number:

$$17602\_{10}=1\color{blue}{000}1\color{blue}{00}11\color{blue}{0000}1\color{blue}{0}\_2$$

$$\begin{array}{c|c} 1&\color{blue}{000}&1&\color{blue}{00}&11&\color{blue}{0000}&1&\color{blue}{0}\\ \hline &3&&2&&4&&1 \end{array}$$

There's exactly one group of consecutive zeros of length **1**, one group of length **2**, one group of length **3** and one group of length **4**.

This is an order-4 Neil number.

More generally:

> An order-\\$n\\$ Neil number is a positive integer whose binary representation contains exactly \\$n\\$ groups of consecutive zeros and for which there's exactly one group of consecutive zeros of length \\$k\\$ for each \\$0\<k\le n\\$, with \\$n\>0\\$.

Clarifications:

* Leading zeros are obviously ignored.
* Groups of consecutive zeros are indivisible (e.g. `000` is a group of length 3 and cannot be seen as a group of length 1 followed by a group of length 2, or the other way around).

## Examples

Order-1 Neil numbers are A030130 (except **0**, which is not a Neil number as per our definition).

The first few order-2 Neil numbers are:

```
18, 20, 37, 38, 41, 44, 50, 52, 75, 77, 78, 83, 89, 92, 101, 102, 105, 108, 114, ...

```

## Your task

Given a positive integer as input, return \\$n\ge 1\\$ if this is an order-\\$n\\$ Neil number or another consistent and non-ambiguous value (*0*, *-1*, *false*, *"foo"*, etc.) if this is not a Neil number at all.

This is .

## Test cases

Using **0** for non-Neil numbers:

```
Input   Output
1       0
2       1
8       0
72      0
84      0
163     0
420     0
495     1
600     3
999     0
1001    2
4095    0
8466    4
16382   1
17602   4
532770  5

```

Or as lists:

```
Input : 1, 2, 8, 72, 84, 163, 420, 495, 600, 999, 1001, 4095, 8466, 16382, 17602, 532770
Output: 0, 1, 0, 0, 0, 0, 0, 1, 3, 0, 2, 0, 4, 1, 4, 5

```

Brownie points if your user ID is a Neil number. :-)

# Answer
> 15 votes
# Charcoal, 21 bytes

```
≔Φ⪪⍘Ｎ²1ιθＩ×Ｌθ⬤θ№θ×0⊕κ

```

Try it online! Link is to verbose version of code. Outputs `0` for irrelevant numbers. Happens to output `1` for `0` as per the OEIS sequence. Explanation:

```
≔Φ⪪⍘Ｎ²1ιθ

```

Convert the input to binary, split on `1`s, and remove empty elements.

```
Ｉ×Ｌθ⬤θ№θ×0⊕κ

```

Check that the array contains all lengths of `0`s and output its length if it does or `0` if it does not.

# Answer
> 9 votes
# Python 2, ~~88~~ 86 bytes

*-2 bytes thanks to @David!*

```
s=sorted([0]+map(len,bin(input()).split("1")[1:]))
n=s[-1]
print(s[~n:]==range(n+1))*n

```

Try it online!

Finds the length of all zero groups, sorts them, and check if the sorted list is `1, 2, 3, ...`

---

Same idea in Python 3.8:

### Python 3.8, ~~85~~ 82 bytes

```
lambda n:(m:=max(s:=sorted(map(len,f"{n:b}".split("1")))))*(s[~m:]==[*range(m+1)])

```

Try it online!

# Answer
> 6 votes
# 05AB1E, ~~16~~ ~~15~~ 13 bytes

```
b1¡€gZ©L¢PΘ®*

```

Outputs `0` as falsey result.

Try it online or verify all test cases.

**Explanation:**

```
b              # Convert the (implicit) input to a binary-string
               #  i.e. 163 → "10100011"
               #  i.e. 420 → "110100100"
               #  i.e. 600 → "1001011000"
 1¡            # Split it on 1s
               #  → ["","0","000","",""]
               #  → ["","","0","00","00"]
               #  → ["","00","0","","000"]
   €g          # Take the length of each chunk
               #  → [0,1,3,0,0]
               #  → [0,0,1,2,2]
               #  → [0,2,1,0,3]
     Z         # Get the maximum (without popping)
               #  → 3
               #  → 2
               #  → 3
      ©        # Store it in variable `®` (without popping)
       L       # Pop an push a list in the range [1,maximum]
               #  → [1,2,3]
               #  → [1,2]
               #  → [1,2,3]
        ¢      # Get the count of each in the list of chunk-lengths
               #  → [0,1,3,0,0] and [1,2,3] → [1,0,1]
               #  → [0,0,1,2,2] and [1,2] → [1,2]
               #  → [0,2,1,0,3] and [1,2,3] → [1,1,1]
         P     # Get the product of that
          Θ    # And check that it's exactly 1
               #  → 0 ==1 → 0 (falsey)
               #  → 2 ==1 → 0 (falsey)
               #  → 1 ==1 → 1 (truthy)
           ®*  # Multiply it by the maximum we stored in variable `®`
               #  → 0*3 → 0
               #  → 0*2 → 0
               #  → 1*3 → 3
               # (after which the result is output implicitly)

```

# Answer
> 5 votes
# APL (Dyalog Extended), 17 bytes

Anonymous tacit prefix function. Any visual similarity with OP is entirely unintentional.

```
(≢×⍳⍤≢≡∘∧≢¨)~⍤⊤⊆⊤

```

Try it online!

The structure and order of execution is as follows:

```
  ┌────────┴───────┐
┌─┼──────┐      ┌──┼──┐
≢ ×  ┌───┼───┐ ~⍤⊤ ⊆  ⊤
    ⍳⍤≢ ≡∘∧ ≢¨
7 8  5   6   4  2  3  1

```

base-Two representation

extract sub-lists according to the runs of 1s in…

`~⍤⊤` negated (0→1, 1→0) base-Two representation

`(``)` apply the following function to that:

`≢¨` the length of each run

`≡∘∧` when sorted, does it (0/1) match…

`⍳⍤≢` the indices of the length?

`×` multiply that by…

the length

# Answer
> 4 votes
# Retina 0.8.2, 54 bytes

```
.+
$*
+`(1+)\1
$1O
(O?1)+
1
O`O+
(^1O|\1O)+1?$|.+
$1
O

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
+`(1+)\1
$1O

```

Begin base 2 conversion, but using `O` instead of `0` as `\10` would be an octal escape.

```
(O?1)+
1

```

As part of base 2 conversion we need to remove one `O` before each `1`. This additionally also collapses all runs of `1`s into a single `1`, which simplifies matching the consecutive runs of `O`s later.

```
O`O+

```

Sort the runs of `O`s in ascending order of length.

```
(^1O|\1O)+1?$|.+
$1

```

Try to match `1O`, then in each repeat match one more `O` than last time, finally matching an optional `1` at the end. If this succeeds, output the last match (including the leading `1`), otherwise output nothing.

```
O

```

Count the `O`s in the last match.

# Answer
> 4 votes
# , 30 24 bytes

```
0(#*/:~-:#\)@-.~#;._1@#:

```

Try it online!

*-6 bytes thanks to Bubbler*

Fittingly, J has been bested here by Neil's Charcoal answer.

# Answer
> 3 votes
# , ~~94~~ ~~85~~ ~~75~~ 74 bytes

```
n=scan();z=rle(n%/%2^(0:log2(n))%%2);N=max(0,s<-z$l[!z$v]);N*all(1:N%in%s)

```

Try it online!

*Edit: -10 bytes thanks to Giuseppe*

*Edit 2: -1 more byte thanks again to Giuseppe*

Finds differences (`diff`) between remainders of each power-of-two (`n%%2^(0:(l=log2(n))`); when sequential remainders are the same, this corresponds to a run of 'zero bits'. `rle` calculates run lengths, and `s` extracts runs of zeros. If `s` contains all the integers up to it's length `N`, then it's a 'Neil number'.

# Answer
> 3 votes
# C (gcc), ~~116~~ \\$\cdots\\$ ~~78~~ 77 bytes

Saved ~~8~~ 11 bytes thanks to ceilingcat!!!
Had to fix a bug, for numbers like \\$84\\$ (\\$1010100\_{2}\\$) which have multiple runs of single \\$0\\$s, which added 3 bytes.
Saved 14 bytes thanks to a suggestion from the man himself Arnauld!!!
Added 6 bytes to fix bugs for numbers with multiple runs of zeros of the same length.

```
c;b;f(n){for(c=3;n;n/=b,c=c&b&~3?n=0:c|b)b=1<<ffs(n);n=ffs(++c)-3;n*=c<8<<n;}

```

Try it online!

Returns \\$n\\$ for an input of an order-\\$n\\$ Neil number or \\$0\\$ otherwise.

**How?**

Performs a bit-wise logical-or summation \\$c=3+\sum{2^{r+1}}\\$, where \\$r\\$ is the length of a zero bit run for all runs in the input number (including zero length runs). Checks to see if we've seen the same non-zero length run before and returns \\$0\\$ if we have. After all the input's zero-bit runs have been added to \\$c\\$ in this manner, \\$c\\$ is tested to see if we've seen \\$n\\$ zero-bit runs of lengths \\$(1,2,\dots,n)\\$ by testing if \\$c\stackrel{?}{=}2^{n+2}-1\\$ and returns \\$n\\$ if this is true, \\$0\\$ otherwise.

# Answer
> 3 votes
# Zsh, 76 bytes

```
for g (${(s[1])$(([#2]$1))#??})((a[$#g]++))
<<<${${${${a/#%/0}:#1}:+0}:-$#a}

```

Try it online!

Explanation:

```
${(s[1])$(([#2]$1))#??}

```

Convert to binary, remove the `2#` prefix, and split the string on `1`, giving us our groups of zeroes.

```
for g ( ... )((a[$#g]++))

```

For each group of zeroes, increment the array at the index given by the length of that string.

```
${a/#%/0}

```

Substitute the array with empty elements filled with zeroes. (If we only increment the array at `a[3]`, then this will set `a[1]=a[2]=0`)

```
${${${${ ... }:#1}:+0}:-$#a}

```

Remove all `1`s. If there is anything left (some a\[n\] != 1), then substitute 0. Otherwise (all a\[n\] = 1) substitute the length of the array.

# Answer
> 3 votes
# Jelly, 12 bytes

```
BŒɠḊm2ṢJƑȧ$Ṫ

```

A monadic Link accepting a positive integer which yields the order (or `0` if not a Neil number).

**Try it online!** Or see the test-suite.

### How?

```
BŒɠḊm2ṢJƑȧ$Ṫ - Link: positive integer, V       e.g. 600
B            - convert V to binary                  [1,0,0,1,0,1,1,0,0,0]
 Œɠ          - run lengths of equal elements        [1,2,1,1,2,3]
   Ḋ         - dequeue                              [2,1,1,2,3]
    m2       - modulo-two slice                     [2,1,3]
      Ṣ      - sort                                 [1,2,3]
          $  - last to links as a monad:
        Ƒ    -   is invariant under?:               1
       J     -     range of length                  (since range(len([1,2,3]))==[1,2,3])
         ȧ   -   logical AND                        [1,2,3]
           Ṫ - tail (if empty yields 0)             3

```

---

Alternative start: `Bṣ1Ẉḟ0ṢJƑȧ$Ṫ`

# Answer
> 2 votes
# Brachylog, 13 bytes

```
ḃḅ{h0&l}ˢo~⟦₁

```

Try it online!

```
 ḅ               Take the runs of
ḃ                the input's binary digits,
  {h0  }ˢ        keep only those that start with 0,
  {  &l}ˢ        and map them to their lengths.
         o       The sorted run lengths
          ~⟦₁    are the range from 1 to the output.

```

Fun fact, my original attempt was `ḃḅo{h0&l}ˢ~⟦₁`, but it mysteriously created a choice point giving me some false positives, so I moved the `o` later to save on a `!`.

# Answer
> 2 votes
# Haskell, 113 bytes

```
g.f
f 0=[0]
f x|h:t<-f$div x 2=[0|odd x]++(h+1-mod x 2):t
g x|n<-maximum x,r<-[1..n]=sum[n|r==[k|k<-r,y<-x,k==y]]

```

Try it online!

# Answer
> 2 votes
# COW, 234 bytes

```
oomMMMMOOOOOmoOMMMMOOMOomoOMoOmOoMMMMOOMMMMOomoOMOomOomOoMoOmoOMMMOOOmooMMMmoomoOmoOMoOmOoMOOmoOMOoMOOMMMmoOmoOMMMMOomoomoOMoOmOoMoOMOOmOomOomoomoOmoOOOOmOoOOOmoomOomOoMMMmoomoOmoOmoOmoOmoOMOOMMMMoOMMMmoOMOoMOOOOOMMMmOomoomoOmooMMMOOM

```

Try it online!

Forms a "string" \\$S\\$ where:

\\$k\in \\{1,\dots,n\\}\\$

* *Even indexes* (or `control cells`) \\$2k-2\\$ serve:
    + to navigate \\$S\\$
    + to know where \\$S\\$ ends
    + to count up to \\$n\\$
* *Odd indexes* (or `k-cells`) \\$2k-1\\$ contain how many consecutive \\$k\\$ zeros there are

The idea is: when a group of consecutive \\$k\\$ zeros is found, its `k-cells` in \\$S\\$ is incremented.
Hence the input is a order-\\$n\\$ Neil number if and only if all `k-cells` are \\$1\\$.
If so, their quantity \\$n\\$ will be returned.
`0` is returned otherwise.

## Explanation

```
moo ]    mOo <    MOo -    OOO *    OOM i
MOO [    moO >    MoO +    MMM =    oom o

[0]: a/2     [1]: a     [2]: a%2     [3]: counter of current group of 0 (k)     [4]: // unused stuff    [5]: S(0)

i=                               ;   Read a in [0], copy
[                                ;   While [0]
    *>=                          ;      Clear [0], paste in [1]
    [                            ;      While [1]
        ->+<=[=->-<<+>=*]=       ;          {REPEATED SUBTRACTION}
    ]                            ;      [0] is a/2, [1] is 0, [2] is a%2
    >>+<                         ;      Increment [3]                                                   // here [3] is k+1
    [                            ;      If [2] {UPDATE THE STRING}                                      // if a%2==1 the current group of 0 it's been truncated
        >-                       ;          Decrement [3]                                                   // [3]-=1 (k)
        [=>>=-]                  ;          While [x] copy it in [x+2] and decrement it                     // moves to control cell 2k-2 and leaves a trail of control cells behind
        >+<                      ;          Increment [x+3]                                                 // k-cell 2k-1 +=1
        +[<<]                    ;          "Open" [x+2], while [x] x-=2                                    // use the trail to return back to [1]
        >>*<*                    ;          Clear [2] and [3]
    ]                            ;
    <<=                          ;   Point to [0], copy
]                                ;
>>>>>                            ;      Point to [5]                                                    // the first control cell in S
[                                ;      While [x] is non-zero                                           // while S has not ended
    =+=                          ;          Paste, increment [x], copy                                  // counting (n)
    >-                           ;          Move to [x+1] and decrement                                     // k-cell-=1
    [                            ;          {NOT A NEIL NUMBER}                                             // iff k-cell is non-zero
        *=<                      ;              Divert the flow (performs this loop 2 times, copy 0)
    ]                            ;              will now break the parent while|
    >                            ;      Point to [x+2]                         |                        // next control cell
]                                ;                                             |
=o                               ;   Paste (n or 0) and print                  v

```

*Cell `[4]` contains the number of groups of consecutive ones that are larger than \\$1\\$, +1 if LSB is 1*.
Nothing relevant for the task, but I couldn't get rid of it staying in this byte count.
Here's a var dump from \[4\].

# Answer
> 2 votes
# Java (JDK), ~~126~~ ~~117~~ 116 bytes

```
q->{int C[]=new int[9],s=0,n=0;for(;q>0;q/=2)C[s]-=q%2<1?(n=++s>n?s:n)-n:~(s=0);while(q++<n)n=C[q]!=1?0:n;return n;}

```

Try it online!

Returns 0 for non-Neil numbers.

I feel like this should be smaller, even though it is in Java.

Ungolfed:

```
q -> {
  int C[] = new int[9],  //C[i] is how many times a streak of length i appeared
      s = 0,             //Length of current streak of zeroes
      n = 0;             //Max streak
  for(; q > 0; q /= 2)   //Go through all of q's digits until q=0
    C[s] -= q % 2 < 1                //If there's a 0 here
            ? (n = ++s > n ? s : n)//Increment s and set n to the max of s and n
               - n      //Subtract n from that because C[s] should stay the same
            : ~(s = 0);  //Otherwise, set s to 0 and add 1 to C[s] (the previous value of s)
  while(q++ < n)           //For every q 0 < q <= n
    n = C[q] != 1 ? 0 : n; //if there was not exactly 1 group of length q, set n to 0
  return n;
}

```

# Answer
> 1 votes
# MATL, 14 bytes

```
BY'w~)SttfX=*z

```

For non Neil numbers the output is `0`.

Try it online! Or verify all test cases.

### Explanation

Consider input `532770` as an example.

```
B     % Impicit input. Convert to binary
      % STACK: [1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0]
Y'    % Run-length encoding. Gives values and run lengths
      % STACK: [1 0 1 0 1 0 1 0 1 0], [1 5 1 4 1 2 1 3 1 1]
w~    % Swap, negate element-wise
      % STACK: [1 5 1 4 1 2 1 3 1 1], [0 1 0 1 0 1 0 1 0 1]
)     % Indexing (use second input as a mask into the first)
      % STACK: [5 4 2 3 1]
S     % Sort
      % STACK: [1 2 3 4 5]
tt    % Duplicate twice
      % STACK: [1 2 3 4 5], [1 2 3 4 5], [1 2 3 4 5]
f     % Find: (1-based) indices of nonzeros
      % STACK: [1 2 3 4 5], [1 2 3 4 5], [1 2 3 4 5]
X=    % Equal (as arrays)?
      % STACK: [1 2 3 4 5], 1
*     % Multiply, element-wise
      % STACK: [1 2 3 4 5]
z     % Number of nonzeros. Implicit display
      % 5

```

# Answer
> 1 votes
# perl -MList::Util=max -MList::Util=uniq -pl, 72 71 bytes

```
@==map{y===c}sprintf("%b",$_)=~/0+/g;$_=(@===max@=)&(@===uniq@=)?0+@=:0

```

Try it online!

Reads a number from the input, convert it to a string with the number in binary format, extracts the sequences of 0, takes their length, then prints the number of sequences of 0s if 1) there are no duplicates, and 2) the max length equals the number of sequences. Else, 0 is printed.

Edit: Saved a byte by replace `&&` with `&` which works, since the result of `==` is `1` or the empty string, which perl treats as `0` if the operator expects a number.

# Answer
> 1 votes
# Perl 5 `-pl`, 61 bytes

```
$a=1;$_=sprintf'%b',$_;$a++while s/10{$a}(?!0)//;$_=!/0/*--$a

```

Try it online!

Converts number to binary, then removes the 0 sequences in order, starting at 1. When it no longer finds a match, that's the Neil number.

# Answer
> 1 votes
# Python 2, 90 bytes

```
a=[len(z)-1for z in sorted(bin(input())[2:].split('1'))if z]
n=len(a)
print(range(n)==a)*n

```

Try it online!

I found almost the same solution as Surculose Sputum.

They had the further insight to get rid of the `[]` so go upvote them :)

# Answer
> 1 votes
# Factor, 146 bytes

```
: f ( n -- n ) >bin [ = ] monotonic-split [ first 48 = ] [ length ] filter-map
natural-sort dup dup length [1,b] >array = [ last ] [ drop 0 ] if ;

```

Try it online!

Not golfy at all with all the mandatory spaces and those long words...

# Answer
> 1 votes
# Wolfram Language (Mathematica), 93 bytes

```
If[Sort[s=Length/@Take[Split@IntegerDigits[#,2],{2,-1,2}]]==Range@If[s=={},t=0,t=Max@s],t,0]&

```

Try it online!

# Answer
> 1 votes
# Haskell, 118 bytes

```
n#0=[n]
n#i|mod i 2<1=(n+1)#div i 2|u<-0#div i 2=n:u
n%[]=n-1
n%x|1/=sum[1|a<-x,a==n]=0|m<-n+1=m%filter(>n)x
(1%).(0#)

```

Try it online!

# Answer
> 1 votes
# Ruby, ~~67 58 57~~ 55 bytes

```
->n{i=0;('%b'%n).scan(/0+/).sort.all?{_1==?0*i+=1}?i:0}

```

Try it online! (+2 bytes because TIO doesn't support ruby 2.7's `_1`)

-2 bytes thanks to Dingus

# Answer
> 1 votes
# Husk, ~~14~~ 10 bytes

```
£ḣ∞0OfΛ¬gḋ

```

Try it online!

-4 bytes from Zgarb.

# Answer
> 1 votes
# Japt, 15 bytes

Returns `0` for falsey.

```
¤ôÍmÊÍf
Ê*UeUÊõ

```

Try it or run all test cases

```
¤ôÍmÊÍf\nÊ*UeUÊõ     :Implicit input of integer                         > 17602
¤                    :To binary string                                  > "100010011000010"
 ô                   :Split at elements that return truthy
  Í                  :  When converted to decimal (0=falsey, 1=truthy)  > ["","000","00","","0000","0"]
   m                 :Map
    Ê                :  Length                                          > [0,3,2,0,4,1]
     Í               :Sort                                              > [0,0,1,2,3,4]
      f              :Filter, to remove 0s                              > [1,2,3,4]
       \n            :Assign to variable U
         Ê           :Length                                            > 4
          *          :Multiplied by
           Ue        :  Test U for equality with
             UÊ      :    Length of U                                   > 4
               õ     :    Range [1,length]                              > [1,2,3,4]
                     :Implicit output of result                         > 4

```

# Answer
> 0 votes
# Io, 124 bytes

Just a port of the 05AB1E answer.

```
method(x,i :=x asBinary lstrip("0")split("1")map(size);if(Range 1 to(i max)map(x,i select(o,o==x)size)reduce(*)==1,i max,0))

```

Try it online!

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


title: How Many Ways To Empty The Glove Box?

text:
# Question
Title: How Many Ways To Empty The Glove Box?
Inspired by this glove-themed 538 Riddler Express Puzzle.

## Task

You are given a positive integer `n`, and a list `A = [a_1, a_2, ..., a_k]` of `k` distinct positive integers.

Then a restricted composition is an ordered list `P = [p_1, p_2, ..., p_m]` where each `p_i` is a (not necessarily distinct) member of `A`, and `p_1 + p_2 + ... + p_m = n`.

So, if `n = 10`, and `A = [2,3,4]` then an example of a restricted composition would be `P = [3,4,3]`. Another example would be `P = [2,3,3,2]`. A third example would be `P = [3,3,4]`. But there's no restricted composition that starts `[3,3,3,...]`, because `10-(3+3+3) = 1`, which is not in `A`.

We want the total number of different restricted compositions given the inputs, as an integer.

## Inputs

A positive integer `n` and a list `A` of distinct positive integers. All reasonable input formats allowed.

## Output

The number of distinct restricted compositions.

## Terms and Conditions

This is ; and thus we seek the shortest submissions in bytes satisfying the constraints. Any use of the usual loopholes voids this contract.

## Test Cases

```
(5, [2, 3, 4]) => 2
(10, [2, 3, 4]) => 17
(15, [3, 5, 7]) => 8

```

# Answer
> 7 votes
# Python 2, ~~50~~ 49 bytes

*-1 byte thanks to @Jonathan Allan*

```
f=lambda n,A:n>=0and(n<1)+sum(f(n-x,A)for x in A)

```

Try it online!

# Answer
> 5 votes
# JavaScript (ES6),  ~~48~~  40 bytes

Takes input as `(a)(n)`.

```
a=>g=n=>n>0?a.map(x=>t+=g(n-x),t=0)|t:!n

```

Try it online!

# Answer
> 4 votes
# , 24 17 bytes

```
1#.[=1#.[:>@,{\@#

```

Try it online!

Recursive version was too verbose in J, so I went brute force.

Take the integers in the right arg as a boxed list and the target number `n` in the left arg.

* `{\@#` \- We create a series of cartesian products of the list with itself, starting with 1 (the list unchanged) and up to `n` (the list crossed with itself n times).
* `[:>@,` We flatten all of those, open them, and sum them.
* `[=` Check which sums equal `n`. This returns a boolean list.
* `1#.` Sum it.

# Answer
> 3 votes
# APL (Dyalog), 18 bytes

Accepts `n` as the right argument and `A` as the left argument.

```
{⍵>0:+/⍺∘∇¨⍵-⍺⋄⍵=0}

```

Try it online!

# Answer
> 3 votes
# Jelly,  ~~6~~  5 bytes

```
ṗⱮẎ§ċ

```

**Try it online!** (Very inefficient.)

### How?

Builds all lists of lengths \\$1\\$ to \\$n\\$ made from the integers in \\$A\\$ and then counts how many sum to \\$n\\$.

```
ṗⱮẎ§ċ - Link: list of positive integers, A; positive integer, n
 Ɱ    - map across x in (implicit range [1..n]) applying:
ṗ     -   Cartesian power -> all length x lists made from values in A
  Ẏ   - tighten (to a list of lists)
   §  - sum each list
    ċ - count occurrences of (n)

```

# Answer
> 2 votes
# K (ngn/k), 23 bytes

```
{$[x>0;+/(x-y)o\:y;~x]}

```

Try it online!

recursive

# Answer
> 2 votes
# Io, 57 bytes

Port of the Python answer.

```
f :=method(n,A,if(n>0,A map(x,f(n-x,A))sum,if(n==0,1,0)))

```

Try it online!

# Answer
> 2 votes
# Husk, ~~10~~ 8 bytes

```
#o=¹ΣuṖ*

```

Try it online!

This is so ridiculously inefficient that it struggles on TIO to even run any of the given test cases: link is to a super-easy test case of n=2, a=\[1,2,3\] (for which output is 4).

Repeats and concatenates (`*`) the input list n times, and then generates all possible subsets (`uṖ` \- this is the slow step!). Then counts the number (`#`) of subsets for which the total equals n (`o=¹Σ`).

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~56~~ ~~49~~ ~~46~~ ~~43~~ 41 bytes

2 bytes golfed thanks to J42161217

```
n_~f~a_=If[n<1,1+Sign@n,Tr[f[n-#,a]&/@a]]

```

Try it online!

Initial solution:

```
Length[Join@@Permutations/@IntegerPartitions[#,∞,#2]]&

```

Try it online!

# Answer
> 1 votes
# Charcoal, ~~21~~ 20 bytes

```
⊞υ¹Ｆθ⊞υ↨Φυ№η⁻⊕ιλ¹Ｉ⊟υ

```

Try it online! Link is to verbose version of code. Edit: Saved 1 byte by using base conversion from 1 instead of summing a potentially empty list. Explanation:

```
⊞υ¹

```

Start our result list with the number of solutions for `n=0` which is always `1` (the empty list).

```
Ｆθ⊞υ

```

Loop `n` times, so that we calculate the results for `1..n`, appending them to the result list.

```
↨Φυ№η⁻⊕ιλ¹

```

Sum those results so far that contribute to the next total. For example, if `A` is `[2, 3, 4]`, then to calculate the result for `n=10`, we already know the results for `n=0..9`, but we only add the results for `n=6`, `n=7` and `n=8`. The sum is calculated by converting from base 1 in case the list is empty.

```
Ｉ⊟υ

```

Print the result for `n`.

# Answer
> 1 votes
# Ruby, ~~40~~ 36 bytes

Python answer port but Ruby strict typing means I can't coerce booleans into integers.

-4 bytes from dingledooper.

```
f=->n,a{n>0?a.sum{|e|f[n-e,a]}:1<<n}

```

Try it online!

# Answer
> 1 votes
# C (gcc), 89 bytes

Port of the Python answer.

Edit: Outgolfed by Noodle9 :/

```
int n;f(int x,int*a){if(x<=0)return!x;int y=0,i=0;while(i++<n)y+=f(x-a[i-1],a);return y;}

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~65~~ 63 bytes

Saved 2 bytes thanks to my pronoun is monicareinstate!!!

```
f(n,a,l,s,i)int*a;{for(s=i=!n;i<l&n>0;)s+=f(n-a[i++],a,l);n=s;}

```

Try it online!

# Answer
> 1 votes
# Perl, 52 bytes

```
$r.=1x$_."|"}{(1x$^I)=~/^($r@){1,$^I}$(?{$\++})(*F)/

```

## Usage

```
printf "2\n3\n4" | perl -p -i10 glovebox.pl

```

## Explanation

Attempts to turn the problem into a string matching one, then uses regex backtracking to do the hard work! In the example given above it ends up constructing a regex match similar to `1111111111 =~ /^(1{2}|1{3}|1{4}){1,10}$(?{$count++})(*F)/`

This will cause the regex engine to attempt each combination of the regex, using `(?{$count++})` to increase `$count` each time the engine matches the input and reaches that point in the pattern, but forcing a fail `(*F)` before the match returns to cause the engine to backtrack and start again with the next combination. `$count` ends up being the answer.

Slightly different approach, was hoping it'd end up a bit shorter though...

# Answer
> 1 votes
# Haskell, 37 bytes

```
n!a|n<0=0|n<1=1|n>0=sum$(!a).(n-)<$>a

```

Try it online!

Quick port of the Python answer, call as `n ! a`.

# Answer
> 1 votes
# 05AB1E, ~~11~~ 7 bytes

```
L€ãO˜¹¢

```

-4 bytes thanks to *@ovs*.

Very slow approach!

Try it online or verify the first two test cases at once (third one times out..).

**Explanation:**

```
L        # Push a list in the range [1, first (implicit) input-integer]
 €       # Map over each integer in this list
  ã      #  Take the cartesian product of the second (implicit) input-list that many times
   O     # Sum each inner-most list
    ˜    # Flatten the list of lists
     ¹¢  # And count how many times the first input occurs in this list
         # (after which the result is output implicitly)

```

---

# 05AB1E, 12 bytes

```
ÅœʒåP}€œ€`Ùg

```

Here a faster (but now way longer) approach using the `Åœ` builtin.

Try it online or verify all test cases.

**Explanation:**

```
Åœ         # Get all lists of positive integer that sum to the (implicit) input-integer
  ʒ        # Filter this list of lists by:
   å       #  Check for each value whether it's in the second (implicit) input-list
    P      #  And check if this is truthy for all of them
  }€œ      # After the filter: get the permutations of each remaining list
     €`    # Flatten one level down
       Ù   # Uniquify the list of lists
        g  # Pop and push the length for the amount of remaining lists
           # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Julia 1.0, 35 bytes

*port of this Python answer*

```
f(n,A)=n>=0&&+(n<1,f.(n.-A,[A])...)

```

Try it online!

# Answer
> 1 votes
# , ~~59~~ 55 bytes

*Edit: -4 bytes thanks to Giuseppe*

```
g=function(t,l,u=t-l)sum(!u,unlist(sapply(u[u>0],g,l)))

```

Try it online!

Recursively removes each element from the glove box, and calls itself with the new total if there's anything left.

# Answer
> 0 votes
# Wolfram Language (Mathematica), 54 bytes

```
Tr[Length/@Permutations/@IntegerPartitions[#,All,#2]]&

```

Try it online!

# Answer
> 0 votes
# Red, ~~81~~ 80 bytes

```
f: func[x y][case[x = 0[1]x < 0[0]on[sum collect[foreach a y[keep f x - a y]]]]]

```

Try it online!

The same recursive approach almost everyone is using, much longer though.

# Answer
> 0 votes
# Racket, ~~74~~ 64 bytes

```
(λ(x y)(if(< x 1)(+(sgn x)1)(apply +(map(λ(a)(f(- x a)y))y))))

```

Try it online!

# Answer
> 0 votes
# Wolfram Language (Mathematica), 36 bytes

```
Tr[Multinomial@@@FrobeniusSolve@##]&

```

Try it online!

---
Tags: code-golf, combinatorics
---


title: Calculate the Kronecker Product

text:
# Question
Title: Calculate the Kronecker Product
Related, but very different.

---

In the examples below, \\$A\\$ and \\$B\\$ will be \\$2\times2\\$ matrices, and the matrices are one-indexed.

A Kronecker *product* has the following properties:

```
A⊗B =  A(1,1)*B   A(1,2)*B
        A(2,1)*B   A(2,2)*B

     =  A(1,1)*B(1,1)   A(1,1)*B(1,2)   A(1,2)*B(1,1)   A(1,2)*B(1,2)
        A(1,1)*B(2,1)   A(1,1)*B(2,2)   A(1,2)*B(2,1)   A(1,2)*B(2,2)
        A(2,1)*B(1,1)   A(2,1)*B(1,2)   A(2,2)*B(1,1)   A(2,2)*B(1,2)
        A(2,2)*B(2,1)   A(2,2)*B(1,2)   A(2,2)*B(2,1)   A(2,2)*B(2,2)

```

**Challenge: Given two matrices, \\$A\\$ and \\$B\\$, return \\$A\otimes B\\$.**

* The size of the matrices will be at least \\$1\times1\\$. The maximum size will be whatever your computer / language can handle by default, but minimum \\$5\times5\\$ input.
* All input values will be non-negative integers
* Builtin functions that calculate Kronecker products or Tensor/Outer products are not allowed
* In general: Standard rules regarding I/O format, program & functions, loopholes etc.

**Test cases:**

```
A =
     1     2
     3     4
B =
     5     6
     7     8
A⊗B =
     5     6    10    12
     7     8    14    16
    15    18    20    24
    21    24    28    32

B⊗A =
     5    10     6    12
    15    20    18    24
     7    14     8    16
    21    28    24    32
------------------------
A =
     1
     2
B =
     1     2

A⊗B =
     1     2
     2     4
------------------------
A =
    16     2     3    13
     5    11    10     8
     9     7     6    12
     4    14    15     1

B =
     1     1
     0     1

A⊗B  =
    16    16     2     2     3     3    13    13
     0    16     0     2     0     3     0    13
     5     5    11    11    10    10     8     8
     0     5     0    11     0    10     0     8
     9     9     7     7     6     6    12    12
     0     9     0     7     0     6     0    12
     4     4    14    14    15    15     1     1
     0     4     0    14     0    15     0     1

B⊗A =
    16     2     3    13    16     2     3    13
     5    11    10     8     5    11    10     8
     9     7     6    12     9     7     6    12
     4    14    15     1     4    14    15     1
     0     0     0     0    16     2     3    13
     0     0     0     0     5    11    10     8
     0     0     0     0     9     7     6    12
     0     0     0     0     4    14    15     1
------------------------

A = 2
B = 5
A⊗B = 10

```

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

```
×€€;"/€;/

```

Uses Büttner's Algorithm (`ü` pronounced when trying to make an `ee` sound \[as in meet\] in the mouth-shape of an `oo` sound \[as in boot\]).

The `;"/€;/` is inspired by Dennis Mitchell. It was originally `Z€F€€;/` (which costs one more byte).

# Answer
> 7 votes
## CJam, 13 bytes

```
{ffff*::.+:~}

```

This is an unnamed block that expects two matrices on top of the stack and leaves their Kronecker product in their place.

Test suite.

### Explanation

This is just the Kronecker product part from the previous answer, therefore I'm here just reproducing the relevant parts of the previous explanation:

Here is a quick overview of CJam's infix operators for list manipulation:

* `f` expects a list and something else on the stack and maps the following *binary* operator over the list, passing in the other element as the second argument. E.g. `[1 2 3] 2 f*` and `2 [1 2 3] f*` both give `[2 4 6]`. If both elements are lists, the first one is mapped over and the second one is used to curry the binary operator.
* `:` has two uses: if the operator following it is unary, this is a simple map. E.g. `[1 0 -1 4 -3] :z` is `[1 0 1 4 3]`, where `z` gets the modulus of a number. If the operator following it is binary, this will *fold* the operator instead. E.g. `[1 2 3 4] :+` is `10`.
* `.` vectorises a binary operator. It expects two lists as arguments and applies the operator to corresponding pairs. E.g. `[1 2 3] [5 7 11] .*` gives `[5 14 33]`.

```
ffff*  e# This is the important step for the Kronecker product (but
       e# not the whole story). It's an operator which takes two matrices
       e# and replaces each cell of the first matrix with the second matrix
       e# multiplied by that cell (so yeah, we'll end up with a 4D list of
       e# matrices nested inside a matrix).
       e# Now the ffff* is essentially a 4D version of the standard ff* idiom
       e# for outer products. For an explanation of ff*, see the answer to
       e# to the Kronecker sum challenge.
       e# The first ff maps over the cells of the first matrix, passing in the
       e# second matrix as an additional argument. The second ff then maps over
       e# the second matrix, passing in the cell from the outer map. We
       e# multiply them with *.
       e# Just to recap, we've essentially got the Kronecker product on the
       e# stack now, but it's still a 4D list not a 2D list.
       e# The four dimensions are:
       e#   1. Columns of the outer matrix.
       e#   2. Rows of the outer matrix.
       e#   3. Columns of the submatrices.
       e#   4. Rows of the submatrices.
       e# We need to unravel that into a plain 2D matrix.
::.+   e# This joins the rows of submatrices across columns of the outer matrix.
       e# It might be easiest to read this from the right:
       e#   +    Takes two rows and concatenates them.
       e#   .+   Takes two matrices and concatenates corresponding rows.
       e#   :.+  Takes a list of matrices and folds .+ over them, thereby
       e#        concatenating the corresponding rows of all matrices.
       e#   ::.+ Maps this fold operation over the rows of the outer matrix.
       e# We're almost done now, we just need to flatten the outer-most level
       e# in order to get rid of the distinction of rows of the outer matrix.
:~     e# We do this by mapping ~ over those rows, which simply unwraps them.

```

# Answer
> 4 votes
# MATLAB / Octave, ~~83~~ 42 Bytes

Saved **41** bytes, thanks to FryAmTheEggman!

```
@(A,B)cell2mat(arrayfun(@(n)n*B,A,'un',0))

```

Test it here!

**Breakdown**

`arrayfun` is a disguised for-loop that multiplies `n*B`, for a variable `n` defined by the second argument. This works because looping through a 2D matrix is the same as looping through a vector. I.e. `for x = A` is the same as `for x = A(:)`.

`'un',0` is equivalent to the more verbose `'UniformOutput', False`, and specifies that the output contains cells instead of scalars.

`cell2mat` is used to convert the cells back to a numeric matrix, which is then outputted.

# Answer
> 1 votes
# Pyth, ~~14~~ ~~12~~ 11 bytes

```
JEsMs*RRRRJ

```

Translation of Jelly answer, which is based on Büttner's Algorithm (`ü` pronounced when trying to make an `ee` sound \[as in meet\] in the mouth-shape of an `oo` sound \[as in boot\]).

Try it online (test case 1)!

### Bonus: calculate `B⊗A` in the same number of bytes

```
JEsMs*LRLRJ

```

Try it online (test case 1)!

# Answer
> 1 votes
# Julia, ~~40~~ ~~39~~ 37 bytes

```
A%B=hvcat(sum(A^0),map(a->a*B,A')...)

```

Try it online!

### How it works

* For matrices **A** and **B**, `map(a->a*B,A')` computes the Kronecker product **A⊗B**.

The result is a vector of matrix blocks with the dimensions of **B**.

We have to transpose **A** (with `'`) since matrices are stored in column-major order.
* `sum(A^0)` computes the sum of all entries of the identity matrix of **A**'s dimensions. For an **n×n** matrix **A**, this yields **n**.
* With first argument **n**, `hvcat` concatenates **n** matrix blocks horizontally, and the resulting (larger) blocks vertically.

# Answer
> 1 votes
# , ~~98~~ 86 bytes

```
function(x,y,`+`=array)aperm(apply(x,1:2,`*`,y)+c(w<-dim(y),v<-dim(x)),c(1,3,2,4))+v*w

```

Try it online!

Reimplementation of `.kronecker` and `outer` for matrices. ~~I do think there's a golfier approach out there, maybe using `apply`?~~ 6 bytes golfed using `apply` and `array` thanks to Dominic van Essen!

The builtins are `%x%` for `kronecker(A,B,"*")` and `%o%` for `outer(A,B,"*")`.

# , 120 bytes

```
function(A,B){l=list()
a=dim(A)
for(i in 1:a[2]-1)l[[i+1]]<-do.call(rbind,lapply(A,"*",B)[1:a+a[2]*i])
do.call(cbind,l)}

```

Try it online!

Naive approach: calculate the subarrays \\$a\_{ij}B\\$ and bind them together in the appropriate order. There are probably golfs here too, but I don't think it'll be shorter than the one above.

# Answer
> 0 votes
# JavaScript (ES6), 79

Straightforward implementation with nested looping

```
(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t

```

**Test**

```
f=(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t

console.log=x=>O.textContent+=x+'\n'

function show(label, mat)
{
  console.log(label)
  console.log(mat.join`\n`)
}

;[
  {a:[[1,2],[3,4]],b:[[5,6],[7,8]] },
  {a:[[1],[2]],b:[[1,2]]},
  {a:[[16,2,3,13],[5,11,10,8],[9,7,6,12],[4,14,15,1]],b:[[1,1],[0,1]]},
  {a:[[2]],b:[[5]]}
].forEach(t=>{
  show('A',t.a)
  show('B',t.b)
  show('A⊗B',f(t.a,t.b))
  show('B⊗A',f(t.b,t.a))
  console.log('-----------------')
})
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
# J, 10 bytes

This is one possible implementation.

```
[:,./^:2*/

```

# J, 13 bytes

This is a similar implementation, but instead uses J's ability to define ranks. It applies `*` between each element on the LHS with the entire RHS.

```
[:,./^:2*"0 _

```

## Usage

```
   f =: <either definition>
    (2 2 $ 1 2 3 4) f (2 2 $ 5 6 7 8)
 5  6 10 12
 7  8 14 16
15 18 20 24
21 24 28 32
   (2 1 $ 1 2) f (1 2 $ 1 2)
1 2
2 4
   2 f 5
10

```

# Answer
> 0 votes
# APL (Dyalog Unicode), 10 bytes

```
{⍪/,/⍺×⊂⍵}

```

Try it online!

### How it Works

```
{  ...   }  ⍝ dfn that takes ⍺=A and ⍵=B
     ⍺×⊂⍵   ⍝ Product of each element of A with all of matrix B
            ⍝ Gives a nested array: an matrix of matrices
   ./       ⍝ Join rows
 ⍪/         ⍝ Join columns

```

---
Tags: code-golf, math, linear-algebra, matrix
---


title: Output nearby primes

text:
# Question
Title: Output nearby primes
Write a program which takes an input (which may or may not be prime), and lists the immediate prime following and preceding it.

**Example input:**

```
1259

```

**Example output:**

```
1249 1277

```

Shortest program wins. Must execute within 10 seconds on a modern desktop PC. Inputs will be limited to 10,000 maximum.

# Answer
> 7 votes
## Perl 5.10 (perl -E), 65 chars

Half the credit (at least) should go to @J B.

```
$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}

```

# Answer
> 15 votes
## *Mathematica*, 19

```
#~NextPrime~{-1,1}&

```

# Answer
> 11 votes
## Mathematica: 28 chars

```
(k=NextPrime;{k[#,-1],k@#})&

```

Usage

```
%[1259]
{1249, 1277}

%[121231313159]
{121231313129, 121231313191}

```

# Answer
> 4 votes
## Python - 93

Based on answer by fR0DDY. I basically merged lines 4 and 5, and shortened line 2 by using a different method.

```
n=input()-1
m=n+2
f=lambda n:any(n%x<1for x in range(2,n))
exec"n-=f(n);m+=f(m);"*m
print n,m

```

# Answer
> 4 votes
## J, 22 characters

```
(_4&p:,4&p:)(".stdin)_

```

# Answer
> 3 votes
**Python ~~116~~ ~~111~~ 109 Characters**

```
n=input()-1
m=n+2
f=lambda n:any(pow(b,n-1,n)>1for b in(3,5,7,13))
while f(n):n-=1
while f(m):m+=1
print n,m

```

# Answer
> 3 votes
# Jelly, 5 bytes

```
Æp,Æn

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Extended), 6 bytes

```
¯4 4⍭⊢

```

Try it online!

I wish I knew a way to shorten this further.

`¯4` and `4` when passed to  give the closest primes to the right argument().

# Answer
> 2 votes
# Swift ~~190~~ ~~187~~ ~~185~~ 110

Swift is very bad in code-golf, but I tried it anyway :D
It's getting shorter and shorter...(Thanks to @HermanLauenstein for removing 75 bytes)

```
var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}

```

# Answer
> 1 votes
# Haskell: 99

```
s(z:y)=z:s[x|x<-y,mod x z>0];f(x:y:z:w)=(x,z):f(y:z:w);p x=(head.filter(\(c,v)->c<x&&v>x).f.s)[2..]

```

Example

```
Main> p 1259
(1249,1277)

```

# Answer
> 1 votes
**Python, 116 139 chars (double indent is tab-char)**

Uses good ole Sieve of Eratosthenes

**Edits** and (thanks a TON @JPvdMerwe). Should work with primes now.

```
l=n=input();a=range(n*2)
for i in a[2:]:a=[k for k in a if k==i or k%i]
for g in a:
 if g>n:print l,g;break
 if i!=n:l=g

```

**Original**

```
a=range(9999)
j=lambda a,n:[i for i in a if i==n or i%n]
for i in a[2:]:a=j(a,i)
o=n=input();
for i in a:
 if o<n and i>n:
  print o,i
 o=i

```

# Answer
> 1 votes
### Scala 119:

```
def p(n:Int)=(2 to n-1).exists(n%_==0)
def i(n:Int,v:Int):Int=if(!p(n+v))n+v else i(n+v,v)
Seq(-1,1).map(i(readInt,_))

```

ungolfed:

```
def notPrime (n:Int) =
    (2 to n-1).exists (n % _ == 0)

def itPrime (n: Int, vector:Int) : Int =
    if (! notPrime (n+vector)) n+vector
    else itPrime (n+vector, vector)

def nearbyPrime (value: Int) =
    Seq (-1, 1).map (sign => itPrime (value, sign))

```

21.2s to run **all** 9998 ints from 3 to 10.000

# Answer
> 0 votes
## Python (123)

```
import Primes as p
j=i=int(input())
n=p.primes(i*2)
while not i in n[:]:
 i+=1
print(i)
while not j in n[:]:
 j-=1
print(j)

```

**NOTE: The `Primes` module was written by me but it existed before this question was asked. It was NOT written for this. Nevertheless, this was deemed unfair, so here is the updated version.**

## Python(215)

```
j=i=int(input())
import math as m
s=list(range(i*2))
for n in s[:]:
 for l in range(1,int(m.ceil(m.sqrt(n)))):
  if(n%l)==0and l!=1and n in s:s.remove(n)
while not i in s:i+=1
print(i)
while not j in s:j-=1
print(j)

```

# Answer
> 0 votes
# Stax, 7 bytes

```
èëïy▌Ü╚

```

Run and debug it

ASCII equivalent:

```
^:Px:pLJ

```

Built-ins.

# Answer
> 0 votes
# JavaScript (Node.js), 79 bytes

```
f=(n,d)=>d?p(n)?n:f(n+d,d):[f(n-1,-1),f(n+1,1)]
p=(n,i=1)=>++i*i>n||n%i&&p(n,i)

```

Try it online!

# Answer
> 0 votes
# C (gcc), ~~98~~ ~~89~~ 87 bytes

-9 bytes thanks to ceilingcat

```
N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}f(n){g(n,-1);g(n,1);}

```

Try it online!

# Full program version, C (gcc), ~~116~~ ~~107~~ 105 bytes

-9 bytes thanks to ceilingcat

```
N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}main(n){scanf("%d",&n);g(n,-1);g(n,1);}

```

Try it online!

# Answer
> 0 votes
# Arn, 22 bytes

```
ét█ï▀¢│B¬Ÿ6├¼òa¡b←Æ╚ÑÕ

```

Try it!

# Explained

Unpacked: `k:((v:#.^2):i)[v?--k v?(k+2`

One of the major weaknesses of Arn (along with operator precedence lmao)

```
  :                     Assign variable
k                       with name of k
    (                   Begin expression
        (
            :
          v
              #.        List of primes from 0 to
                  _     Variable initialized to STDIN; implied
                ^       exponentiated by
                  2     Literal two
        )               End expression
      :i                Index of
        _               implied
    )
[                       Begin sequence
    v
  ?                     Indexed by
    --k                 k minus 1
    v
  ?
    (
        k
      +                 Plus
        2
    )                   implied
]                       End of sequence; implied

```

# Answer
> 0 votes
# 05AB1E, 6 bytes

```
ÅMsÅN»

```

Try it online!

```
ÅMsÅN»  # full program
     »  # join...
ÅM      # nearest prime less than...
        # implicit input...
     »  # with...
   ÅN   # nearest prime greater than...
  s     # implicit input...
     »  # by a newline
        # implicit output

```

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


title: A naturally occurring prime generator

text:
# Question
Title: A naturally occurring prime generator
There are quite a large number of prime generating functions. Pretty much all of them are constructed and are based on the sieve of Eratosthenes, the Möbius function or the Wilson's theorem and are generally infeasible to compute in practice. But there are also generators, that have a very easy structure and were found by accident.

In 2003 Stephen Wolfram explored a class of nested recurrence equations in a live computer experiment at the NKS Summer School. A group of people around Matthew Frank followed up with additional experiments and discovered an interesting property of the simply recurrence

```
a(n) = a(n-1) + gcd(n,a(n-1))

```

with the start value of `a(1) = 7`. The difference `a(n) - a(n-1) = gcd(n,a(n-1))` always seemed to be 1 or a prime. The first few differences are (OEIS A132199):

```
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, ...

```

If we only omit the 1s we get the following sequence (OEIS A137613):

```
5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3,
941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, ...

```

Eric S. Rowland proved the primeness of each element in this list a few years later. As you can see, the primes are mixed and some of them appear multiple times. It also has been proven, that the sequence includes infinitely many distinct primes. Furthermore it is conjectured, that all odd primes appear.

Because this prime generator was not constructed but simply found by accident, the prime generator is called "naturally occurring". But notice that in practice this generator is also quite infeasible to compute. As it turns out, a prime p appears only after `(p–3)/2` consecutive 1s. Nevertheless implementing this prime generator will be your task.

# Challenge:

Write a function or a program that prints the first `n` elements of the sequence `A137613` (the sequence without the 1s). You can read the input number `n >= 0` via STDIN, command-line argument, prompt or function argument. Output the first `n` elements in any readable format to STDOUT, or return an array or a list with these values.

This is code-golf. Therefore the shortest code wins.

# Leaderboard:

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language. To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
var QUESTION_ID=55272;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
```

# Answer
> 20 votes
# Pyth, 14 13 bytes

```
meaYhP+sY-5dQ

```

Uses `a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))` where `Lpf` means least prime factor.

Try it here online.

# Answer
> 7 votes
# Python 3.5.0b1+, ~~95~~ 93 bytes

Link to Python 3.5.0b1+ release

```
import math
def f(k,n=2,a=7,L=[]):x=math.gcd(n,a);return k and f(k-1%x,n+1,a+x,L+1%x*[x])or L

```

A direct implementation of the recurrence, featuring:

* Our good friend `1%x`, and
* `math.gcd`, as opposed to `fractions.gcd`.

# Answer
> 5 votes
# Julia, 110 bytes

```
n->(a(n)=(n≥1&&(n==1?7:a(n-1)+gcd(n,a(n-1))));i=2;j=0;while j<n x=a(i)-a(i-1);x>1&&(j+=1;println(x));i+=1end)

```

Ungolfed:

```
function a(n::Int)
    n ≥ 1 && (n == 1 ? 7 : a(n-1) + gcd(n, a(n-1)))
end

function f(n::Int)
    i = 2;
    j = 0;
    while j < n
        x = a(i) - a(i-1)
        if x > 1
            j += 1
            println(x)
        end
        i += 1
    end
end

```

# Answer
> 5 votes
# PHP, ~~101~~ ~~96~~ ~~99~~ ~~98~~ ~~77~~ 72 bytes

```
<?for(;2>$t=gmp_strval(gmp_gcd(~++$i,7+$e+=$t))or$argv[1]-=print"$t ";);

```

**Usage:**
Call the Script with an argument: `php -d error_reporting=0 script.php 30`
If you want to test it you need to uncomment `;extension=php_gmp.dll` in your php.ini
--\> `extension=php_gmp.dll`
Should I add the extension to my byte count? Any thoughts?

**Log:**
Saved 3 bytes thanks to Ismael Miguel.
Saved 26 bytes thanks to primo.

# Answer
> 4 votes
# Pyth, 30 bytes

Very badly golfed, can be considerably reduced. Defines recursive function at front, filters `.f`irst-n, and then maps the difference.

```
L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

```

Try it here online.

# Answer
> 4 votes
# Julia, ~~69~~ 67 bytes

```
n->(i=1;a=7;while n>0 x=gcd(i+=1,a);a+=x;x>1&&(n-=1;println(x))end)

```

This is a simple iterative solution to the problem. `x` is the difference (which is the `gcd`), and then I update `a` by adding `x`.

# Answer
> 4 votes
# Haskell, 51 bytes

```
d=zipWith gcd[2..]$scanl(+)7d
f=($filter(>1)d).take

```

Note that `f` is a function that will return the first *n* elements.

Rather than computing the `a(n)` and then working out the differences, we compute the differences `d(n)` and sum them together to get `a(n)`. (Those unfamiliar with Haskell may protest that we need `a(n)` first in order to get `d(n)`, but of course lazy evaluation gets us around this problem!)

Ungolfed:

```
a = scanl (+) 7 d        -- yielding a(n) = 7 + d(1) + d(2) + ... + d(n-1)
d = zipWith gcd [2..] a  -- yielding d(n) = gcd(n+1, a(n))

f n = take n $ filter (> 1) d -- get rid of 1s and take the first n

```

# Answer
> 3 votes
# JavaScript (ES6), 91

Recursive gcd, iterative main function. Not so fast.

Usual note: test running the snippet on any EcmaScript 6 compliant browser (notably not Chrome not MSIE. I tested on Firefox, Safari 9 could go)

```
F=m=>{
  for(G=(a,b)=>b?G(b,a%b):a,o=[],p=7,n=1;m;d>1&&(o.push(d),--m))
    p+=d=G(++n,p);
  return o
}

O.innerHTML=F(+I.value)
```

```
<input id=I value=10><button onclick='O.innerHTML=F(+I.value)'>-></button>
<pre id=O></pre>
```

# Answer
> 3 votes
# Haskell, 74 71 66 bytes

```
f=($filter(>1)$tail>>=zipWith(-)$scanl(\x->(x+).gcd x)7[2..]).take

```

Used the trick here: https://codegolf.stackexchange.com/a/39730/43318, and made point-free.

(Previous: 71 bytes)

```
a=scanl(\x->(x+).gcd x)7[2..]
f m=take m$filter(>1)$zipWith(-)(tail a)a

```

First make the sequence of a's, and then take the differences.

(Previous: 74 bytes)

```
f m=take m$filter(>1)$map snd$scanl(\(x,d)->(\y->(x+y,y)).gcd x)(7,1)[2..]

```

Standard list functions, plus clever use of lambda function. Note this is 1 byte shorter than the more obvious

```
g m=take m$filter(>1)$map snd$scanl(\(x,d)n->(x+gcd x n,gcd x n))(7,1)[2..]

```

If we don't count imports, I can get this down to 66.

```
import Data.List
h m=take m$filter(>1)$snd$mapAccumL(\x->(\y->(x+y,y)).gcd x)7[2..]

```

# Answer
> 3 votes
## PARI/GP, 60 bytes

```
a(n)=a=7;i=1;while(n,if(1<d=gcd(i+=1,a),n-=1;print(d));a+=d)

```

Taken more or less straight from the definition ***a(n) - a(n-1) = gcd(n, a(n-1))***

Output for `a(20)`:

```
5
3
11
3
23
3
47
3
5
3
101
3
7
11
3
13
233
3
467
3

```

# Answer
> 3 votes
# APL (Dyalog Extended), 24 bytes

```
{⍵<2:5⋄⊃⍭6-⍵-+/∇¨⍳⍵-1}¨⍳

```

`{⍵<2:5⋄⊃⍭6-⍵-+/∇¨⍳⍵-1}` dfn to calculate the nth element

`⍵<2:5` if ⍵\<2 return 5

else

`∇¨⍳⍵-1` recursively find the first ⍵-1 terms

`+/` sum them

`6-⍵-s` in APL is 6-(⍵-s) = 6-⍵+s, as APL is evaluated right to left

`⊃⍭` take the first (least) prime factor

`¨⍳` apply the function to the first n numbers, to find the first n elements

Try it online!

Old answer: 46 bytes

```
{l←⍵⋄{l≡≢r←1~⍨2-⍨/⍵:r⋄∇⍵,(+/(0,1+≢)∨1↑⌽)⍵}7 8}

```

Try it online!

# Answer
> 3 votes
# Jelly, 13 10 bytes

```
’ßS_+6ÆfḢ)

```

Try it online!

*Edit: I decided to revisit my oldest answer and found out that it can be very trivially golfed by 3 bytes. I sure have improved…*

Uses the formula `a(n) = Lpf(6-n+sum{i=1,...,n-1}a(i))`.

## Explanation

```
’ßS_+6ÆfḢ)   Main monadic link
         )   Map over the range [1..n]:
’              Decrement
 ß             Recursively apply this link
  S            Sum
   _           Subtract n
    +6         Add 6
      Æf       Prime factorization
        Ḣ      First element

```

# Answer
> 2 votes
# C++, ~~193~~ ~~182~~ ~~180~~ 172 bytes

Thanks @Jakube - saved 8 bytes on output.

```
int g(int a,int b){return a==b?a:a>b?g(b,a-b):g(a,b-a);}void f(int *r,int n){int m=1,i=0,a=7,b;while(i<n){b=g(a,++m);if(b>1){r[i]=b;++i;}a+=b;}}int main(){int r[6];f(r,6);}

```

# Answer
> 2 votes
# Mathematica, 59 bytes

```
For[i=j=1;a=7,i<=#,,d=GCD[++j,a];If[d>1,Print@d;i++];a+=d]&

```

# Answer
> 2 votes
# Husk, 13 bytes

```
↑¡ö▼p+6§-LΣ;5

```

Try it online!

Uses Shevelev's formula from A137613: `a(n) = Lpf(6-n+sum{i=1,...,n-1}a(i))`.

```
↑               # input-th element of
 ¡              # list of repeated application of
  ö             # 4 functions:
   ▼            # minimum of
    p           # prime factors of
     +6         # 6+
          Σ     # sum of list so far
       §-L      # minus length of list so far
           ;5   # starting with 5

```

# Husk, 18 bytes

```
↑f←Ẋ-¡λS+ȯ⌋→L¹→);7

```

Try it online!

Alternative derivation (following the story of the question): difference between adjacent elements of `a(n) = a(n-1) + gcd(n,a(n-1))` with `a(1)=7`, ignoring `1`s.

```
↑                   # input-th element of
 f←                 # (without 1s)
   Ẋ-               # differences between adjacent elements of
     ¡              # list of repeated application of
      λ        )    # this function:
       S+     →     # sum of last element of list so far, plus
         ȯ⌋         # gcd of
           →        # last element of list so far, and
            L¹      # length of list so far
                ;7  # starting with 7

```

# Answer
> 1 votes
# Japt `-g`, 12 bytes

```
n6+UÆßXÃÅx)k

```

Try it

Uses the LPF formula from the OEIS entry with a little bit of Japt trickery: when reducing a 2D-array by addition Japt just grabs the first element of each sub-array\*.

```
n6+UÆßXÃÅx)k     :Implicit input of integer U
n                :Subtract U from
 6+              :  6 plus
   UÆ            :  Map each X in the range [0,U)
     ßX          :    Recursive call with argument U=X
       Ã         :  End map
        Å        :  Slice off the first element
         x       :  Reduce by addition (of first elements)
          )      :End subtraction
           k     :Prime factors of result
                 :Implicit output of first element of final array

```

\*Or, for those interested, what actually happens is that each sub-array is run through JavaScript's `parseFloat` function coercing them to comma delimited strings and then `parseFloat` parses that string to an integer until it hits an illegal character, i.e. the first comma.

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


title: Map inputted ASCII characters

text:
# Question
Title: Map inputted ASCII characters
> Be sure to see the other challenge, Reverse ASCII character map!

The ASCII charset (American Standard Code for Information Interchange) is the most widely-used character encoding standard. ASCII codes represent text in computers, telecommunications equipment, and other devices.

# Challenge

Your challenge is to print a mapping of the ASCII character set as the user inputs them. GIF:

After the user enters every ASCII character, the output should look like this:

# Mapping

Each character has an assigned position on a 16x6 logical grid, starting with the space character in the top left position, and wrapping such that the digit 0 appears below it.

When printable ASCII input is received, print that ASCII character at its assigned screen location without deleting any of the characters currently onscreen.

# Rules

* Your program only needs to map out the printable ASCII characters, `0x20` to `0x7E`.
* Your program must not terminate and continue to map characters to the screen until all printable ASCII characters have been inputted. From here, your program can either terminate or run off into Neverland.
* Your program can map characters any way you like, e.g. to a spreadsheet, table, console window, or a graphical window.
* No matter how you display the mapping, it must be updated in realtime (as soon as it receives user input).
* If your program does not read input silently, it must put the cursor out of the way, so the text won't get in the way of the map.

# Help

Here is the pseudocode algorithm I used to generate the GIF:

```
loop forever
    c = input
    y_coord = c / 16
    x_coord = c - y * 16
    if c is printable
        print c at (x_coord * 2 + 1, y_coord + 1)
    end if
end loop

```

There may be another way to achieve the required output. You can choose to use my algorithm or your own, but the output must be the same regardless.

Here's a useful ASCII table reference.

# Scoring

The answer with the least bytes in each language wins. Have fun!

# Answer
> 3 votes
## QBIC, ~~53~~ 57 bytes

Added 4 bytes for the spacing.

```
{locate 7,1┘_?┘i=asc(A)┘locate i/16-1,(i%16+1)*2┘?chr$(i)

```

QBIC began development as a shorthand for QBasic, so I thought translating my QBasic answer would demonstrate this nicely. We've saved some 40% in the byte-count for a functionally identical program - and that's even when `LOCATE`, `ASC`, and `CHR` have no QBIC-functions yet. Fortunately, QBIC can pass code directly to QBasic to compensate for this. A side-by-side:

```
QBIC              QBASIC
------------      ------------
{                 DO
locate 7,1        LOCATE 7,1
                  note that the lower-case alphabet is left unaltered in QBIC.
_?                LINE INPUT A$  (LINE INPUT used instead of INPUT to handle comma's)
i=asc(A)          i=ASC(A$)
locate i/16-1     LOCATE i/16-1
   ,(i%16+1)*2       ,(i MOD 16+1)*2
?chr$(i)          ?CHR$(i)
                  LOOP   (implicitly added to QBIC at EOF)

```

# Answer
> 19 votes
## JavaScript (ES6) + HTML, 114 + 16 = 130 bytes

*Saved 16 bytes thanks to @Shaggy*

```
a=Array(96).fill` `;onkeypress=k=>(a[k.key.charCodeAt()-32]=k.key,O.innerText=a.join` `.match(/.{1,32}/g).join`
`)
```

```
<pre id=O></pre>
```

It's so unbelievably satisfying to just mash the keyboard...

# Answer
> 16 votes
## QBasic 4.5, ~~81~~ 85 bytes

*Added 4 bytes to comply with the spacing-rule.*

```
DO
LOCATE 7,1
LINE INPUT A$:i=ASC(A$)
LOCATE i\16-1,(i MOD 16+1)*2
?CHR$(i)
LOOP

```

And the output will look like this (NOTE: Old screenshot, now every character is separated by a space):

QBasic has the `LOCATE` command, which comes in handy here. A breakdown of this code:

```
DO                          Starts an infinite loop
LOCATE 7,1                  Moves the cursor out of the way
LINE INPUT A$:i=ASC(A$)     LINE INPUT gets user input; we need LINE INPUT instead of regular input
                            for support of <space> and <comma>. The ASC() function then takes the
                            ASCII value of the first character in the input, so it can deal with
                            inputs like 'Hello' - it will take ASC('H') and assign that to 'i'
LOCATE i\16-1               Here's the cool bit: LOCATE takes a row and a column to put the cursor on.
    ,(i MOD 16+1)*2         Row is determined by dividing the ASC value by 16, minus 1 (SPACE, ASC 32
                            is placed on row 1), and for columns we take the modulo plus 1 (Again, SPACE
                            mod 16 = 0, plus 1 = column 1). Multiplied by 2 gives us the spacing.
                            We move the cursor to 1,2
?CHR$(i)                    PRINT a cast of the ASCII value to CHR at the specified location.
LOOP                        Ad infinitum

```

# Answer
> 8 votes
# Java 8, 143 bytes

```
o->{for(;;){char c=System.console().readPassword()[0];if(c>31&c<127)System.out.println(String.format("\u001B[%d;%df%c",c/16+1,(c%16+1)*2,c));}}

```

Uses the ANSI control code `CSI n ; m f` to set the cursor position and `Console.readPassword()` to read the user input silently. Output of some characters:

# Answer
> 7 votes
# BrainFuck, 355 Bytes

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

```

BrainFuck's options are pretty limited, so output is in the terminal and the screen is "cleared" with 20 newlines. Input should be the ASCII characters, separated by newlines.

Try it online!

## Formatted and Documented

These are the debug notes I used to write the program. I used my interpreter which can optionally print the state of the tape at every '~' character for debugging.

```
[
    run.bf
    codegolf.stackexchange.com/questions/124306/map-inputted-ascii-characters
]

[
    Calculate 16 * 6
    Resulting tape state:
    [0 0 0 0 0 0 16 96 0 0 0 0 ...]
               ^
    Note that, to obtain a 16-by-6 grid, the 16
    immediately to the right is decreased to 15
    (since we will decrease it by 1 each loop
    until we reach 0 and immediately reset)
]
>>>>++++[->++++[->+>++++++<<]<]>~

[
    Our next goal is to make 96 sets of 3 cells each in the pattern [C D 0]
    The first cell will represent an entered character--when the corresponding
    input on the keyboard is pressed, it will change to the entered key.
    The first cell is initialized to 32 (' ').

    The second cell will represent the delimiter after that character.
    Every 16 cells, this should be 10 for '\n'. Otherwise, it should be 32 for ' '.

    The third cell is a buffer cell, used for traversal of the grid. In general,
    it should be only temporarily modified and then reset to 0.
]

>->[-<
    [
       -<<<<++++[->++++++++<]
       [
           The second cell of our 3-set should be 32, so the above line
           writes 32 to the 3rd cell from the beginning of the tape (0-indexed)
       ]
    ]
    >>>
    [
       <<<[ The second cell of our 3-set should be 10, and we must reset the line counter ]
       <<++++++++[->>++<<<+>]>>-<<<++>>
    ]

    [ At this point, the delimiting cell we need is two cells to the left. ]
    <<[>>>>>>[>>>]>+<<<<<[<<<]<<-]

    >>>>>>[>>>]++++[-<++++++++>]
    [ Debug Mode: In the previous loop, add a + in the string of 8 +'s to get visible spaces in the grid ($-signs) ]
    >[-<+>]<<[<<<]>>
]

[ Go back to the beginning of the tape and clear up the residual '15' ]
<[-]~

<<,

[
    [->+>+<<],[-]++++[->>--------<<]

    [
        Take input such that the state of the tape now looks like this:
        [0 0 0 0 0 c c-32 0 32 32 0 32 32 0 32 32 0 ...]
                 ^
        Where 'c' was the entered character.
        We now set up 1's in the buffer zones of the first c-32
        3-sets and clear the character that is currently there.
        All that is left, then, is to copy c to that location.
    ]

    [ Set up the row of 1's. ]
    >>[>>>>[>>>]+[<<<]<-]

    [ Clear the current character. ]
    >>>>[>>>]<<[-]~<[<<<]

    [ Copy the new character. ]
    <<[>>>>>[>>>]<<+<[<<<]<<-]

    [ Clean up the 1's. ]
    >>>>>[>>>]~<<<[[-]<<<]

    [ Print the grid. ]
    >[.>.>>]~

    [ Print a bunch of newlines ]
    ++++++++++[->+>++<<]>>[-<.>]<[-]

    [ Take a new input. ]
    <<<<[<<<]<,
]

```

# Answer
> 6 votes
## Mathematica, 108 bytes

```
a=" "~Table~16~Table~6;Dynamic@Grid@a
((a[[⌊#/16⌋-1,#~Mod~16+1]]=i)&@ToCharacterCode[i=Input[]];#0[])&[]

```

Try it online at https://sandbox.open.wolframcloud.com/

When you paste code and press `Shift+Enter`, a dialog box will pop up, you enter `"a"` for example for character `a`. The program runs forever.

Note: On Wolfram sandbox, the font is formatted differently from that in Mathematica in my computer. So the line/column spacing may looks weird.

# Answer
> 5 votes
# Python 2, 115 bytes

```
s='\n'.join([' '*31]*6)
while 1:
 c=input();i=ord(c)
 if 31<i<128:i-=32;i=i%16*2+i//16*32;s=s[:i]+c+s[i+1:];print s

```

Try it online!

Requires quotation marks (single or double) around the inputted characters (the TIO version does not).

# Answer
> 4 votes
# str, noncompeting, 18 bytes

Presenting my new semi-esoteric language.

```
#C;dby16#/~2-~u#pq

```

```
#C;dby16#/~2-~u#pq
..;                   preamble
#C                    clear screen
   ...............    main program; each character is pushed to the stack before
   d                  duplicate
    b                 buffer the character
     y                convert to character code
      16#/            divmod by 16 (a / b, a % 6)
          ~2-~        subtract a / b by 2
              u       unbuffer the character
               #p     place that character in the given position
                 q    "quiet"; disable auto-printing

```

# Answer
> 3 votes
## Haskell, 133 bytes

```
p=putStr.("\27["++)
g l=do c<-getChar;p"2J";mapM h(c:l);g(c:l)
h c|(y,x)<-divMod(fromEnum c)16=p$show y++';':show(2*x+1)++'H':[c]
g[]

```

Requires a terminal that understands ANSI escape sequences.

It's shorter to keep a list of all keys pressed so far and clearing the screen before printing all of them each round than turning off the echo in the terminal session. The latter needs `import System.IO` and `hSetEcho stdin(2<1)` which costs too many bytes.

# Answer
> 3 votes
# C, 101 bytes

```
c,y,x;f(){while(~(c=getchar()))printf("\e[1;20H"),y=c/16,x=c-y*16,printf("\e[%d;%dH%c",y+1,x*2+1,c);}

```

This was the program I used to make the graphics. Output is as shown in the GIF. ;)

# Answer
> 3 votes
# QBasic, ~~62~~ 58 bytes

```
a=ASC(INPUT$(1))
LOCATE a\16-1,1+2*(a MOD 16)
?CHR$(a)
RUN

```

Tested with QB64. Should work fine on regular QBasic, too, although you may want to modify it to do a `CLS` on the first run.

Similar to steenbergh's answer, but uses `INPUT$(1)` to read characters one at a time. This approach is shorter and also displays no prompt. It also uses `RUN` for the infinite loop, since we don't have to store any state between iterations except the state of the screen.

# Answer
> 2 votes
# Ruby, ~~79~~ ~~75~~ 71 + 13 = 84 bytes

+13 bytes for `-rio/console` flag.

```
loop{$/+=STDIN.getch
97.times{|n|print$/[(n+31).chr]||" ",["
"][n%16]}}

```

## Ungolfed

```
loop {
  $/ += STDIN.getch
  97.times {|n|
    print $/[(n+31).chr] || " ", ["
"][n%16]
  }
}

```

# Answer
> 1 votes
## Pascal, 112 chars

```
Uses crt;var c:char;Begin ClrScr;repeat c:=ReadKey;GotoXY(ord(c)and$F*2+1,ord(c)shr 4-1);write(c);until 1<0;End.

```

As my Mathematica solution takes many bytes in `div`, `mod` and `ToCharacterCode[Input[]]`, I try making another answer with Pascal. But without `ClrScr` my compiler (FPC) left some compile information on the screen. `ClrScr;` takes 7 bytes.

The `*2` used for proper spacing takes another 2 bytes.

# Answer
> 1 votes
## LOGO, 90 bytes

```
cs
rt 90
keyboardon[invoke[setxy 30*modulo ? 16 -30*int ?/16 label char ?]keyboardvalue]pu

```

Try it on FMSLogo.

After all, my Logo solution is the shortest, compared with my Mathematica and Pascal answer.

Add 3 bytes if the turtle is required to be hidden.

# Answer
> 1 votes
# 6502 machine code + Apple //e ROM, 31 bytes

Hex dump:

```
8000- 20 58 FC 20 0C FD 48 38
8008- E9 A0 48 29 0F 0A 85 24
8010- 68 4A 4A 4A 4A 20 5B FB
8018- 68 20 ED FD 4C 03 80

```

Commented assembly:

```
 1 HTAB     =     $24        ; HORIZONTAL POSITION OF CURSOR
 2 SETVTAB  =     $FB5B      ; SETS VERTICAL POSITION OF CURSOR FROM ACC
 3 COUT     =     $FDED      ; OUTPUTS CHARACTER IN ACC
 4 HOME     =     $FC58      ; CLEARS SCREEN
 5 RDKEY    =     $FD0C      ; GETS CHARACTER FROM KEYBOARD, STORES IN ACC
 6          ORG   $8000
 7          JSR   HOME
 8 GETINP   JSR   RDKEY
 9 * POSITION CURSOR
10          PHA              ; PRESERVE ACC
11          SEC              ; MAKE SURE CARRY IS SET TO SUBTRACT
12          SBC   #" "       ; SUBTRACT CHAR CODE OF SPACE
13          PHA              ; SAVE ACC
14          AND   #$0F       ; GET LOWER 4 BITS TO GET CURSOR X POSITION
15          ASL              ; SHIFT LEFT TO MAKE SPACES BETWEEN CHARS
16          STA   HTAB
17          PLA              ; GET OLD ACC
18          LSR              ; SHIFT HIGH NIBBLE
19          LSR              ; INTO LOW NIBBLE
20          LSR              ; TO GET CURSOR Y POSITION
21          LSR
22          JSR   SETVTAB
23          PLA              ; RESTORE ACC
24 *
25          JSR   COUT
26          JMP   GETINP

```

If the cursor invalidates it, here's a 36-byte version without a cursor:

```
8000- 20 58 FC AD 00 C0 10 FB
8008- 8D 10 C0 48 38 E9 A0 48
8010- 29 0F 0A 85 24 68 4A 4A
8018- 4A 4A 20 5B FB 68 20 ED
8020- FD 4C 03 80

```

# Answer
> 1 votes
# SmileBASIC 3, 82 bytes

```
CLS
@L
C$=INKEY$()IF""!=C$THEN V=ASC(C$)-32LOCATE V MOD 16*2,V DIV 16*2?C$;
GOTO@L

```

In the SmileBASIC character set, `¥` is located where `\` normally would be; hopefully this doesn't invalidate this answer completely.

# Answer
> 1 votes
# Japt, ~~63~~ 43 bytes

Seeing as I apparently have a reputation for making Japt do things it shouldn't be able to do (continuous input, in this case), golfing from my my phone, and golfing with a feed of beer inside me, it's high time I combined all 3 of those things!

```
;$oninput=$@OqE¬ËoOx`Í*s.value` 1Ãú ò16 m¸·

```

Test it (just start typing in the "Notes" field)

# Answer
> 0 votes
# Applesoft BASIC, 134 bytes

```
0TEXT:HOME:PR#0
1C=PEEK(49152):POKE49168,0:HTAB1:VTAB20:NORMAL:IFC>=128THENC=C-128:INVERSE
4Y=INT(C/16):X=C-Y*16:HTABX*2+1:VTABY+1:IFC>=32THEN PRINTCHR$(C):IFC<32THEN PRINTCHR$(127)
9GOTO1

```

This is a golfed version of the Apple \]\[ keyboard test, the program that inspired the challenge.

# Answer
> 0 votes
# 8086 machine code, MS-DOS .COM, 27 bytes

Runnable in DOSBox. The only assumption about register starting values is `AH = 0`, which is true for most DOS isotopes. This, and the fact that only BIOS interrupts are used, means it can be run from a boot sector by changing the first instruction to `mov ax, 3` (and the `org` of course) at the terrible, terrible cost of one byte.

Expects only printable ASCII characters as input. Does not terminate.

## Binary

```
00000000 : B0 03 CD 10 31 C0 CD 16 50 2C 20 D4 10 D0 E0 92 : ....1...P, .....
00000010 : B4 02 CD 10 58 B4 0E CD 10 EB E9                : ....X......

```

## Assembly

```
org 0x100
cpu 8086

    mov al, 3       ; Set video mode to 80x25 text
    int 0x10        ; Has the desired side-effect of clearing the screen

main_loop:
    xor ax, ax      ; Read keystroke into AX
    int 0x16        ; AH = scan code, AL = ASCII

    push ax         ; Save ASCII code for later
    sub al, 32      ; Make ASCII code into range 0..94
    aam 0x10        ; AH = AL / 16 (row), AL = AL % 16 (col)
    shl al, 1       ; Double column for spacing

    xchg ax, dx     ; Move cursor to proper position
    mov ah, 2
    int 0x10

    pop ax          ; Retrieve ASCII code
    mov ah, 0x0e    ; Output at cursor position
    int 0x10

    jmp main_loop

```

---
Tags: code-golf, ascii-art, printable-ascii, interactive
---


title: Tips for golfing in Scala 3

text:
# Question
Title: Tips for golfing in Scala 3
What general tips do you have for golfing in Scala 3? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Scala 3 (e.g. "remove comments" is not an answer). Please post one tip per answer.

Also see Tips for golfing in Scala

# Answer
> 2 votes
# Use parameter untupling

Parameter untupling allows you to write functions accepting a single tuple as input as if they were functions accepting 2 parameters. Basically, you can replace these

```
list.map{case(a,b)=>a+b}
//and
list.map{case(a,b)=>Seq(a,b)}
//or
list.map(t=>t._1+t._2)
//and
list.map(t=>Seq(t._1,t._2))

```

with this, which is both shorter and more beautiful.

```
list.map(_+_)
//and
list.map(Seq(_,_))

```

# Answer
> 2 votes
# Use @main and toplevel functions

If you need to make a full program, use the `@main` annotation on a toplevel main method.

```
@main def m={code}

```

It's a lot shorter than these 2 approaches:

```
object M extends App{code}
object M{def main(a:Array[String])={code}}

```

# Answer
> 2 votes
# Optional braces

In match expressions, at least, you can save a byte by using indentation-based syntax.

```
a match
case b=>c
case d=>e

```

is 27 bytes, while the below code is 28.

```
a match{case b=>c case d=>e}

```

As a side note, `match` also gets special treatment when it comes to chaining. The following Scala 2 code:

```
("foo"match{case x=>x})match{case x=>x}

```

can now be written without the parentheses:

```
"foo"match{case x=>x}match{case x=>x}

```

# Answer
> 1 votes
# Leave out `new` with universal apply methods

You can call constructors without using `new` (like Kotlin), treating all classes as if they have `apply` methods in their companions. This saves 4 bytes every time you instantiate something, since `new Foo()` becomes just `Foo()`.

This also applies to givens (although you rarely need them for code golf):

```
given foo as Foo=new Foo() //bad
given foo as Foo=Foo()     //better
given foo as Foo           //great

```

# Answer
> 1 votes
# Numeric Literals

Edit: As @stewSquared pointed out, this only works in experimental releases now

You can now write a number literal for any user-defined type with a given/implicit instance of the `FromDigits` trait, such as `BigInt` and `BigDecimal`.

In Scala 2, to pass the number 9,999,999,999,999,999 to a function accepting `BigInt`s, you would have to use `BigInt("9999999999999999")`, but now you can just directly say `9999999999999999` without using the apply method or constructor explicitly.

You can also use underscores, scientific notation, hex, etc., just like any normal number literal, as long as the `FromDigits` instance for that type supports that notation, of course. Both `BigInt` and `BigDecimal` are okay with underscores, but only `BigInt` allows hex, and only `BigDecimal` allows scientific notation (with decimals).

# Answer
> 0 votes
# Use match types for recursive functions that pattern match

Making a typealias with a match type is sometimes shorter than using a proper function. For example, take this implementation of the KI calculus (not an actual thing). The type doesn't need `:Any`, so you save 7 bytes in all (`type` is 1 byte more than `def`).

```
//A normal function
def r(t:Any):Any=t match{case(('K',x),y)=>r(x)case('I',x)=>r(x)case t=>t}
//With match types
type R[T]=T match{case(('K',x),y)=>R[x]case('I',x)=>R[x]case _=>T}

```

Admittedly, in this particular example, you could use auto-tupling, `->`, pattern-matching function literals, etc. to make the def shorter, but this is just one case. When you're not dealing with tuples, or the return type is more complex than just `Any`, or you have multiple parameters, this tip becomes more useful.

# Use type constructors for two-argument functions

When you define a type with two type parameters, you can treat it like an infix operator. Not so for methods. Suppose you have the following two definitions

```
def>(a:Int,b:Int)=...
type +[A,B]=...

```

When you invoke `>`, you can call it with `>(a,b)`, whereas for `+`, you can call it like `A+B`. You can use any other operator you want if you want a specific precedence.

# Answer
> 0 votes
# New Control Syntax

In most cases, the new control syntax doesn't shorten code (and is actually more verbose), it comes in handy in for comprehensions. If your expression or pattern ends or starts with a parentheses or double quote, you can save a byte or two:

```
for((x,y,z)<-Seq((1,2,3),(3,4,5));y<-"foo")yield y+x  //Old-style syntax
for(x,y,z)<-Seq((1,2,3),(3,4,5));y<-"foo"yield y+x    //New control syntax

```

It's not as useful as some other things, like parameter untupling, but I often find myself using for comprehensions for function calls like `f(foo)` or `Seq(1,2)`, which end in parentheses.

See it run in Scastie.

---
Tags: code-golf, tips, scala
---


title: Palindromic Primes without 11

text:
# Question
Title: Palindromic Primes without 11
> Every palindrome with an even number of digits is divisible by 11, so 11 is the only \[palindromic prime\] with an even number of digits. - David Wasserman, OEIS

I learned this today the manual way, before I did my research, when my program skipped numbers with an even number of digits (except 11) when calculating palindromic primes. Your task: create a program or function that when given an integer input N, outputs the Nth term in Stephen's Palindromic Sequence™.

# Stephen's Palindromic Sequence™

Stephen's Palindromic Sequence™ starts with 11, and continues with palindromic semiprimes divisible by 11. Basically, all of the semiprimes that would be primes if 11 didn't "count." The upside is that this list contains numbers with an even number of digits! Yay. And, a lot of numbers with an odd number of digits are skipped, since they were already prime.

The beginning of the sequence:

```
1   : 11
2   : 22
3   : 33
4   : 55
5   : 77
6   : 121
7   : 737
8   : 979
9   : 1111
10  : 1441
11  : 1661
12  : 1991
13  : 3113
14  : 3223
15  : 3443
16  : 3883
17  : 7117
18  : 7447
19  : 7997
20  : 9119
21  : 9229
22  : 9449
23  : 10901

```

\*Although 1331 (11^3) and similar fit the spirit of this sequence, they do not fit the rules.

Longer test cases:

```
26  : 91619
31  : 103301
41  : 139931
51  : 173371
61  : 305503
71  : 355553
81  : 395593
91  : 725527
101 : 772277
127 : 997799
128 : 1099901
141 : 3190913
151 : 3739373
161 : 7589857
171 : 9460649
200 : 11744711
528 : 39988993

```

# Input

Integer N, \>= 1. You can use a 0-indexed N (be sure to adjust test cases) if you specify so in your answer. Trailing newlines allowed.

# Output

The Nth term in Stephen's Palindromic Sequence™. Trailing newlines allowed.

# Rules

* The only input your program/function can take is N. Your program cannot, for example, fetch a sequence from OEIS (aka standard loopholes apply).
* You must be able to print an output up to six digits (N=127). Time is not a factor - however, if your program/function gets very long very fast, you must prove that the algorithm works. If your language naturally allows longer outputs, it you can let it expand naturally up to its limit, or cap it at ten digits, whichever you prefer. Output/termination beyond your limit does not matter, as long as it does not appear to be a valid output.
* Program/function function on invalid input is irrelevant.

# Answer
> 3 votes
# Husk, 12 bytes

```
!:11foṗ/11İ↔

```

Try it online!

```
!               # get element at input-th index of
 :11            # prepend 11 to
          İ↔    # palindromic numbers
    fo          # that satisfy
       /11      # when they're divided by 11
      ṗ         # the result is a prime

```

# Answer
> 17 votes
# Python 2, ~~76~~ ~~73~~ ~~72~~ ~~70~~ ~~69~~ 68 bytes

```
n=input();c=k=m=11
while n:m*=k/c;k+=c;n-=`k`==`k`[::~m%k-c]
print k

```

*Thanks to @WheatWizard for golfing off 3 bytes!*

*Thanks to @ØrjanJohansen for golfing off 1 byte!*

*Thanks to @xnor and @ØrjanJohansen for paving the way to 68 bytes!*

Input is 0-indexed. Try it online! or verify the first 31 test cases.

### Background

Recall that Wilson's theorem states that for all integers **p \> 1**,

meaning that **(p - 1)! + 1** is evenly divisible by **p** if and only if **p** is prime.

If **p \> 1** is *not* prime, it is composite; let **q** be the smallest prime divisor of **p**. Clearly, **q ≤ p/q**. There are two cases:

* If **q = p/q**, we have that **p = q²**.

If **q = 2**, **(p - 1)! = 3! = 6**, so **(p - 1)!** is congruent to **2** modulo **p**.

If **p/q = q \> 2**, so **2q \< p**. This way, **q** and **2q** are both among **1, …, p - 1**, whose product is the factorial of **p - 1**, so **2p = 2q² = q · 2q** divides **(p - 1)!** evenly.
* If **q \
 1**.

Now, for all integer congruences and all integers **a**, **b**, and **c**, the following holds.

When **a = -1**, **b = 11**, and **c = -1**, we follow that

and, since **21** and **-23** are congruent modulo **44** and **-1** and **11p-1** are congruent modulo **11p**, we arrive at the following conclusion.

For all possible values of **p**, the outcome (**11**, **21**, or **11p - 1**) will fall in the range **0, …, 11p - 1**, so these values match those that will be returned by Python's `%` operator.

### How it works

We initialize **c**, **k**, and **m** to **11** after the saving the input in **n**. **c** will be constant for the remainder of the program. Since there are three occurrences of **c** on the following line and assigning **c** costs only two bytes, this saves a byte. **k** can be thought of **11p** using the meaning of **p** from the previous paragraph; initially, **k = 11 = 11 · 1!**. **m** takes the place of **11 · (p - 1)!**; initially, **m = 11 = 11 · 0!**. **k** and **m** will satisfy the relationship **m = 11 · (k/11)!** at all times.

**n** represents the number of “Stephen's palindromes” we have to find. Since **k = 11** initially, we can output **k** verbatim without further computation. However, when **n** is positive, we enter the while loop. The loop begins by multiplying **m** by **k/c = p**, then adding **11** to **k**, thus incrementing **p**. If **k** is a member of the sequence, we subtract **1** from **n** and start over. Once **n** reaches **0**, we found the sequence member at the desired index and break out of the loop, then print the last value of **k**.

The expression

```
`k`==`k`[::~m%k-c]

```

performs the actual test, and it's result (*True* / **1** for sequence members, **0** / *False* otherwise) is subtracted from **n**. As seen before, **~m % k = (-m - 1) % k = (-11 · (p - 1)! - 1) % 11p** equals **10** if **p** is prime, **21** if **p = 4**, and **11p - 1 \> 43** if **p \> 4** is composite. Thus, after subtracting **c = 11**, we're left with **-1** for prime **p** and a positive integer larger than **9** otherwise.

For prime **p**, ``k`[::-1]` gives us the string representation of **k** with reversed digit order, so comparing it to ``k`` checks whether **k** is a palindrome. If it is, all conditions are fulfilled and **k** is a sequence member. However, if **p** is not prime, the large range step and the fact that **k** will always have more than one digit mean that ``k`[::-1]` cannot have the same number of digits as ``k``, let alone be equal to it.

# Answer
> 9 votes
# Jelly, ~~18~~ 13 bytes

```
ṬÆẸ×©11ŒḂµ#ṛ®

```

For some reason, this is much slower than my initial revision, despite doing exactly the same.

Try it online!

### N = 127

```
dennis-home:~$ time jelly eun 'ṬÆẸ×©11ŒḂµ#ṛ®' <<< 127
997799

real    1m43.745s
user    1m43.676s
sys     0m0.113s

```

### How it works

```
ṬÆẸ×©11ŒḂµ#ṛ®  Main link. No arguments.

         µ     Combine all links to the left into a chain.
          #    Read an integer n from STDIN and call the chain monadically, with
               argument k = 0, 1, 2, ... until n values of k result in a truthy
               output. Return the array of all matching values of k.
Ṭ                Untruth; yield [0, 0, 0, ..., 1] (k-1 zeroes followed by a 1) or
                 [] if k = 0.
 ÆẸ              Unexponents; consider the resulting array as exponents of the
                 sequence of primes and yield the corresponding integer. For k = 0,
                 this yields 1. For k > 0, it yields the k-th prime.
   ×©11          Multiply the result by 11 and copy the product to the register.
       ŒḂ        Test if the product is a palindrome.
           ṛ®  Replace the resulting array with the integer in the register.

```

# Answer
> 9 votes
# Brachylog, 17 bytes

```
:I{11|ṗ×₁₁≜.↔}ᶠ⁽t

```

Try it online!

This is 1-indexed.

### Explanation

```
:I{          }ᶠ⁽t    Find the Input'th result of the following:
   11                  Output = 11
     |                 Or
          ≜.           Output is an integer…
      ṗ×₁₁             …which is the result of multiplying a prime by 11…
           .↔          …and Output reversed is still the Output

```

Two realizations with this answer:

* I need to fix the fact that superscript passing to metapredicates (with ) does not work if there is no input to pass (which is why I have to add `:I`).
* I need to add a metapredicate to get the `N`th result of a predicate (which would avoid using `ᶠ⁽t` and instead e.g. `ⁿ⁽`).

Implementing both changes would make that answer 14 bytes.

# Answer
> 5 votes
## Mathematica, ~~65~~ 60 bytes

```
n=NextPrime;11Nest[n@#//.x_/;!PalindromeQ[11x]:>n@x&,1,#-1]&

```

Iterates directly through primes using `NextPrime` and checks whether 11 times the prime is a palindrome. Works up to **N = 528**. The results 528 and 529 are more than 216 primes apart, at which point `//.` will fail to attempt a sufficient number of substitutions.

# Answer
> 4 votes
# Python 2, ~~111~~ ~~107~~ ~~103~~ ~~102~~ ~~101~~ ~~100~~ ~~91~~ ~~90~~ 89 bytes

Dennis has me beaten here, so go check out his answer.

This answer is zero indexed

```
n=input()
r=1
while n:r+=1;c=`r*11`;n-=all(r%x for x in range(2,r))*c==c[::-1]
print r*11

```

Try it online!

*One byte saved thanks to math junkie*

## Explanation

First we take input and set it to `n` we also make a new variable `r=1`. We will count up `r` searching for palindromes that are the product of a prime and 11. Each time we find one we will decrement `n` until it reaches 0.

So we start a the loop:

```
while n:

```

The first thing we do is increment `r`

```
r+=1

```

We also predefine a variable `c` as the string representation of `r*11`

```
c=`r*11`

```

Now we want to decrement `n` if we have found such a number. We will simply subtract a boolean representing if `r*11` fits the pattern from `r`. If this is `False` we will subtract zero and if it is `True` it will subtract 1.

To calculate the boolean we do:

```
all(r%x for x in range(2,r))*c==c[::-1]

```

The first part `all` will determine if `r` is prime. We multiply the result by `c` if `r` is prime this will just be `c` but if `r` is composite it will be `""`, the empty string. We then compare this to `c[::-1]` which is the reverse of `c`. If `r` is prime and `c` is a palindrome this will be `True`, if either fails the whole thing will evaluate as false.

When `n` is zero we simply `print c`.

# 83 bytes

Here is a recursive solution that is shorter but unfortunately doesn't meet the specs because it hits python's recursion cap too fast.

```
f=lambda n,r=1:n and f(n-all(r%x*(`r*11`==`r*11`[::-1])for x in range(2,r)),r+1)+11

```

Try it online!

# Answer
> 4 votes
# 05AB1E, 15 bytes

0-indexed.

```
11Iµ11N*DÂQNp*½

```

Try it online!

**Explanation**

```
11               # initialize stack with 11
  Iµ             # loop over N in [1 ... inf] until counter equals input
    11N*         # multiply N by 11
        D        # duplicate
         ÂQ      # check if the copy equals its reverse
           Np    # check if N is prime
             *   # multiply the results of the checks together
              ½  # if 1, increase counter

```

# Answer
> 3 votes
# Haskell, ~~94~~ 90 bytes

```
h#n|n<2=0|mod n h<1=1+h#div n h|j<-h+1=j#n
([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!)

```

Try it online! Example usage: `([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127`.

`[0,11..]` constructs the infinite list `[0,11,22,33, ...]` (the zero is needed to make the sequence 1-indexed). For each `n` in this list we check `n==(read.reverse.show)n`, that is whether `n` is a palindrome. `3>2#n` checks if `n` has at most two prime divisors. Because `n` is always divisible by 11, we don't get any real primes but only semiprimes.

**Edit:** Thanks to Ørjan Johansen for golfing 4 bytes!

# Answer
> 2 votes
# PHP, 82 Bytes

```
for(;$d<$argn;$i>1||($p=11*$n)!=strrev($p)?:$d++)for($i=++$n;--$i&&$n%$i;);echo$p;

```

Try it online!

# Answer
> 1 votes
# Axiom, 105 bytes

```
g(n)==(i:=c:=1;repeat(c=n=>break;i:=i+1;if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1)));i*11)

```

ungolf, test code and results

```
f(n)==
   i:=c:=1
   repeat
      c=n=>break
      i:=i+1
      if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1))
   i*11

(5) -> [[i,g(i)]  for i in 1..23]
   (5)
   [[1,11], [2,22], [3,33], [4,55], [5,77], [6,121], [7,737], [8,979],
    [9,1111], [10,1441], [11,1661], [12,1991], [13,3113], [14,3223], [15,3443],
    [16,3883], [17,7117], [18,7447], [19,7997], [20,9119], [21,9229],
    [22,9449], [23,10901]]
                                          Type: List List PositiveInteger
(6) -> [[i,g(i)]  for i in [26,31,41,101,151,200]]
   (6)
   [[26,91619], [31,103301], [41,139931], [101,772277], [151,3739373],
    [200,11744711]]

```

Here g(700)=92511529 so the limit would be \>700; ww(1000)=703999307 but using nextPrime()

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