# Question
Title: Find all Perrin pseudoprimes less than 100 million
Simply put, the Perrin sequence has the following recurrence relation:

> P(n) = P(n-2) + P(n-3);
>
> P(0) = 3; P(1) = 0; P(2) = 2;

But wait!! There's more!!

The Perrin sequence has a very bizarre property:

> If N is prime, then P(N) mod N = 0.

Furthermore, there are very few composite numbers which have this property. This can serve as a simple primality test which gives very few false positives.

There are 5761462 numbers under 100 million which satisfy this congruence. Out of those, 5761455 (99.9999%) are prime numbers.

Your mission is to compute those 7 numbers which pass the test but which are not prime. To be specific, your program must output these numbers in a reasonable format:

```
271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

```

You can find more perrin pseudo primes (all of them up to 10^16) with factorization here. For this challenge only the first 7 are important, since they are the only one smaller than 100 million.

(Your program must *compute* these numbers without having them pre-made, or accessing the internet, or similar stuff.)

Also, your program should not produce integer overflows. This may at first seem difficult because the 100 millionth Perrin number is really, really big. Algorithms do exist, however, which would not cause overflows.

This is code golf, shorter solutions are better.

# Answer
> 2 votes
# Ruby, 183

```
require'Prime'
f=->a{a=a.flat_map{|n|String===n ? n : n<3?%w[3 0 2][n]:[n-2,n-3]} until a.all?{|x|String===x}
a.map(&:to_i).inject :+}
n=1
p n if f[[n+=1]]%n==0&&!n.prime? while n<1e8

```

Technically works but runs in an unreasonable amount of time. Try setting the lower bound to 271435 and upper bound to 271450.

# Answer
> 1 votes
### GolfScript, 53 50 characters

```
10 8?,{3 0 2{@2$+3$%}4$2-*])!*},{.,2>{1$\%!},*},n*

```

Do not try to run this version - it'll take very long time to complete (if ever). The code creates a list of all candidates and then consists of two filter steps, first to select all assumed primes and then filter all non-primes from the remaining list. In order to see the code work you can try the following snippet:

```
30,{271430+}%
.p
{3 0 2{@2$+3$%}4$2-*])!*},
.p
{.,2>{1$\%!},*},
p

```

# Answer
> 1 votes
## PARI: 148

The oeis webpage on the Perrin number contains a PARI code written by Joerg Arndt that can easily be modified (a number & spacing) to fit the criteria

```
N=10^8;
default(primelimit, N);
M=[0,1,0;0,0,1;1,1,0];
a(n)=lift(trace(Mod(M,n)^n));
{for(n=1,N,if(isprime(n),next());if(a(n)==0,print1(n,",");););}

```

It takes quite a while, but it definitely works. I will work on translating this to Fortran for speed computation, but it definitely will not be small (especially if I put the prime test in the code & not as a `use <module>` declaration).

# Answer
> 1 votes
## Python (127)

```
a=i=3
b,c=0,2
while i<10**8:
    c,b,a=a+b,c,b
    j=2
    if c%i==0:
        while j*j<=i:
            if i%j==0:print i;break
            j+=1
    i+=1

```

Unnecessary usage of memory avoided but the solution tends to be slow due to big integer operations. Primality testing is done with a slow algo.

# Answer
> 1 votes
## AutoHotkey 132

```
o:={-2:1,-1:-1,0:3}
loop % 10**8
{
p:=0
if !Mod(o[(l:=A_index)-2]+o[l-3],l)
loop % l
if !Mod(l,A_index)
p++
if p>2
s.=l ","
}
msgbox % s

```

Not possible as Integer limit is surpassed.

# Answer
> 1 votes
# Husk, 22 bytes

```
↑7fo¬ṗtW¬z%Ntƒ(+d302Ẋ+

```

(Don't bother to) Try it online!: as many other answers this is extremely slow, so you won't see anything in the 60s TIO allows. Try this online instead! for a modified version that finds the first Perrin pseudoprime after 271440 (yes, it's 271441).

### Explanation

```
↑7fo¬ṗtW¬z%Ntƒ(+d302Ẋ+
             ƒ(+d302Ẋ+    Recursive definition of the Perrin sequence:
                d302       Start with the digits of 302
               +           and append after them
                    Ẋ+     the pairwise sums
             ƒ             of the sequence itself
            t             Drop the first value (we like counting from 1 in Husk)
         z%N              Compute each value modulo its index
       W¬                 Find the indices of 0s
      t                   Drop the fist one (0 mod 1 is 0, but for some reason
                           1 is not one of the required outputs)
  f                       Keep only those values
   o¬                     that are not
     ṗ                    primes
↑7                        Take the first 7 results

```

# Answer
> 0 votes
# Haskell (169)

```
p=3:0:2:zipWith(+)p(tail p)
s(x:y)=x:s[a|a<-y,a`rem`x/=0]
s[]=[]
w=s$2:[3,5..10^8]
k(y,x)z|x`rem`y==0&&(y`notElem`w)=y:z|1<2=z
main=print.foldr k[]$zip[2..10^8].drop 2$p

```

`p` is an infite list producing the Perrin numbers, `s` is a simple sieve function, `w` contains all primes up to 10^8. `k` checks whether the pair `(y,x)` (where `y` is the Perrin number's index and `x` is the number itself) fulfils the condition and adds them to the list `z`. `main` folds `k` along the zip of the list `[2..10^8]` and the Perrin numbers (except for N=0 and N=1).

Don't run this program. It will generate the prime numbers first, which takes *very*, **very**, ***very*** long due to the inefficient sieve. Faster versions would use a wheel sieve and a binary search instead of the current linear search. Also, starting at around 10^5, garbage collection will eat up almost all productivity.

# Answer
> 0 votes
# Perl 68

```
use ntheory":all";forcomposites{say if is_perrin_pseudoprime($_)}1e8

```

Takes 66 seconds on my macbook with the latest version, 6 minutes with previous one (that had no prefilters -- basically a sped up version of Arndt's Pari code).

Of course this is cheesy by using a module that does all the work in C. 88 lines of C with prefilters for faster operation, 28 lines if removing the filters and an optimization to avoid mulmod for small inputs.

# Answer
> 0 votes
# Jelly, 30 bytes

```
Ø.’ịṖS;@
Ø.Ḥ3;Ç⁸¡ị@‘
Ẓ=Ç%$Ɗ8#Ḋ

```

Try it online!

Wildly inefficient, times out on TIO before printing anything.

## How it works

```
Ø.’ịṖS;@    - Helper link. Takes a list l on the left
            - l is the list of previous Perrin numbers and the link appends the next Perrin number
Ø.’         - Yield [-1, 0]
    Ṗ       - Remove the last element of l
   ị        - Index into the cropped version of l
            - This gives the second and third elements from the end of l
     S      - Take the sum of these two
      ;@    - Append to l

Ø.Ḥ3;Ç⁸¡ị@‘ - Helper link. Takes an integer k on the left
            - This link takes an integer k and returns the kth Perrin number
Ø.          - Yield [0, 1]
  Ḥ         - Double to [0, 2]
   3;       - Prepend 3
      ⁸¡    - Do the following k times, operating on the list [3, 0 2]:
     Ç      -   Call the above helper link
          ‘ - Yield k+1
        ị@  - Take the 1-indexed (k+1)th index of this list

Ẓ=Ç%$Ɗ8#Ḋ   - Main link. Takes no arguments
     Ɗ8#    - Do the following over n = 0, 1, 2, ... until 8 values return True:
Ẓ           -   Is n prime?
    $       -   Group the previous two links and run over n:
  Ç         -     Get the nth Perrin number
   %        -     Modulo it by n
 =          -   Are the two values equal?
            -   The two values will either be equal if:
            -     n is prime and P(n) mod n = 1 or
            -     n is composite and P(n) mod n = 0 or
            -     n = 1
            -   The first is never true, therefore this only returns True if n is composite and P(n) mod n = 0 or n = 1
            - This returns [1, 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291]
        Ḋ   - Remove 1 from this list

```

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


title: Toggle Shift Key

text:
# Question
Title: Toggle Shift Key
# Objective

Given an ASCII character, toggle its "shift-ness" on the standard US keyboard (ANSI-INCITS 154-1988 (R1999)), then output it.

# Mapping

```
) ↔ 0
! ↔ 1
@ ↔ 2
# ↔ 3
$ ↔ 4
% ↔ 5
^ ↔ 6
& ↔ 7
* ↔ 8
( ↔ 9
" ↔ '
+ ↔ =
, ↔ <
- ↔ _
. ↔ >
/ ↔ ?
: ↔ ;
(Capital Latin letters) ↔ (Small Latin letters)
[ ↔ {
\ ↔ |
] ↔ }
` ↔ ~
(ASCII whitespaces and control characters are left intact)

```

# Rule

* Non-ASCII characters fall into *don't care* situation.

# Examples

Given a character `0`, output `)`.
Given a character `C`, output `c`.
Given a character  (space), output .
Given a character `\t` (horizontal tab), output `\t`.
Given a character `\a` (bell), output `\a`.

# Answer
> 9 votes
# x86-16, Genuine IBM PC, ~~32~~ ~~31~~ 29 bytes

```
00000000: b4f0 8ec0 bfe5 e8b3 3ab1 74a0 8200 f2ae  ........:.t.....
00000010: 3acb 7f02 f7db 268a 41ff cd29 c3         :.....&.A..).

```

Build with `xxd -r`.

**Unassembled listing:**

```
B4 F0       MOV  AH, 0F0H               ; BIOS segment address (F000H)
8E C0       MOV  ES, AX                 ; set ES to BIOS segment for SCASB
BF E8E5     MOV  DI, E8E5H              ; set to LABEL K10
B3 3A       MOV  BL, 58                 ; size of table
B1 74       MOV  CL, 58*2               ; size of both tables
A0 0082     MOV  AL, BYTE PTR DS:[82H]  ; get input char from command line
F2/ AE      REPNZ SCASB                 ; search BIOS table for char
3A CB       CMP  CL, BL                 ; found in the lowercase table?
7F 02       JG   UPPER                  ; if so, convert with uppercase table by adding
F7 DB       NEG  BX                     ; otherwise subtract the offset
        UPPER:
26:8A 41 FF MOV  AL, ES:[BX+DI-1]       ; get char from table
CD 29       INT  29H                    ; DOS fast write to console
C3          RET                         ; return to DOS

```

**Input/Output:**

**How does it work?**

Well, the PC BIOS already contains all of the code and tables necessary for this since it actually handles the conversion of scan codes received from the keyboard to ASCII chars (in real/DOS mode at least). There's no way (that I know of) to actually hook this on just *any* "PC-compatible" BIOS, however if you know the location of the table in ROM (on the IBM PC it starts at `F000:E8E5`), you can use that.

On Page A-25 of Appendix A the IBM PC Technical Reference (listing of the entire source code of the PC BIOS) is the disassembly of this table:

Unfortunately, this address will be different on any given PC-clone BIOS and of course, there's no guarantee that it would even be implemented in the same way by anyone else. Thus, this submission is guaranteed to run only on a *Genuine IBM PC*. Go Big Blue!

# Answer
> 9 votes
# JavaScript (Node.js),  ~~110 ... 97~~  96 bytes

```
c=>(s=")0@2^6&7*8(9\"'+=-_:;`~")[s.indexOf(c)^1]||(B=Buffer)([([n]=B(c),n%127>32)<<4+n/64^n])+''

```

Try it online!

### How?

We use a lookup table for these pairs:

```
) ↔ 0
@ ↔ 2
^ ↔ 6
& ↔ 7
* ↔ 8
( ↔ 9
" ↔ '
+ ↔ =
- ↔ _
: ↔ ;
` ↔ ~

```

For all other characters, we use the following code:

```
(B = Buffer)([   // generate a buffer from a singleton array:
  (              //
    [n] = B(c),  //   n = ASCII code of the input character
    n % 127 > 32 //   1 if 32 < n < 127, or 0 otherwise
  )              //
  << 4 + n / 64  //   left-shifted by 4 if n < 64, or by 5 otherwise
  ^ n            //   XOR'ed with n
]) + ''          // end of Buffer(); coerce it to a string

```

which supports these 3 cases:

* If \\$32\<n\<64\\$, we XOR the ASCII code with \\$16\\$, which is what we need for:

```
! ↔ 1
# ↔ 3
$ ↔ 4
% ↔ 5
, ↔ <
. ↔ >
/ ↔ ?

```
* If \\$64\le n\<127\\$, we XOR the ASCII code with \\$32\\$, which toggles the case of letters and also works for these pairs:

```
[ ↔ {
\ ↔ |
] ↔ }

```
* If \\$n\le32\\$ or \\$n=127\\$, the character is left unchanged (ASCII code XOR'ed with \\$0\\$).

# Answer
> 7 votes
# Retina 0.8.2, 34 bytes

```
T`-~A-]d';-?/.+,:"(*&^%$#@!)}-_`Ro

```

Try it online! Link includes test cases.

Explanation: The `T` command is Retina's transliteration operation. Among its special characters are:

* ```: Delimit the parts of the command
* `-`: Introduce a range (this suppresses the following special characters so `d-o` just means `defghijklmno`)
* `_`: Delete the matching character
* `d`: `0-9`
* `R`: Reverse the next range
* `o`: Take the source string as the range

The trick is therefore to create as many ranges as possible to reduce the length, plus avoiding having the `-` and `_` characters where they would be interpreted as a special character and avoiding the ``` at all by including it inside a range. Additionally arranging for the range to transliterate to its reversal allows that to be expressed very cheaply.

# Answer
> 4 votes
# Bash \+ core utilities, ~~58~~ \\$\cdots\\$ ~~51~~ 49 bytes

Added ~~47~~ 50 bytes to fix a bug kindly pointed out by Giuseppe.
Saved 8 bytes thanks to Value Ink!!!
Saved 2 bytes thanks to Mitchell Spector!!!

```
a='"A-]`=<_>?)!@#$%^&*(;'
b=\'a-~+-:
tr $a$b $b$a

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Extended), 86 bytesSBCS

This solution has been out-golfed but is preserved due to being interesting for its sourcing of the data.

Anonymous prefix lambda. Requires 0-based indexing (`⎕IO←0`).

```
{⍵∊a←↑'[!-~]{2}'⎕S'&'↓⍉↑'\w\w...'⎕R(5⍴'')↓11 71↑30↓⎕FMT⌂notes.keyboards:a⌷⍨~@1⊃⍸⍵=a⋄⍵}

```

Try it online!

This works by extracting the character pairs from a built-in note about keyboards.

`{``}` "dfn"; argument character is :

`⌂notes.keyboards` the built-in string

`⎕FMT` ForMaT as a character matrix

`30↓` drop the first 30 lines

`11 71↑` take the first 11 lines' first 71 columns

split into list of strings

`'\w\w...'⎕R(``)` PCRE **R**eplace word-character,word-character,any-symbol,any-symbol with:

`''` the empty string

`5⍴` reshaped to length 5, padding with spaces; i.e. 5 spaces

mix list of strings into character matrix

transpose

split matrix into list of strings

`'[!-~]{2}'⎕R'&'` PCRE **S**earch and return any pair of printable ASCII characters

mix list of character pairs into two-column matrix

`a←` store in `a` (for ***a****ll*)

`⍵∊``:` if the argument character is a member of that matrix:

`⍵=` Boolean matrix mask where they are equal

get indices where true

pick the first (row,column) pair

`~@1` negate the number at position 1 (the column; i.e. 1→0 and 0→1)

`a⌷⍨` use that to index into the matrix of **a**ll pairs

else:

the argument character

# Answer
> 3 votes
# Python 3, ~~99~~ 95 bytes

Same strategy as @Arnauld's answer.

*-4 bytes thanks to @mypetlion*

```
lambda c,s=")0!1@2#3$4%5^6&7*8(9\"'+=,<-_.>/?:;[{\\|]}`~":[c.swapcase(),s[s.find(c)^1]][c in s]

```

Try it online!

## Explanation

* `s=")0!1@2#3$4%5^6&7*8(9\"'+=,<-_.>/?:;[{\\|]}`~"` contains all pairs of special toggles.
* `s[s.index(c)^1]` gets the index of the other character from the same pair
* If the character is a Latin or control character (`c in s` is `False`), `c.swapcase()` is returned. `c.swapcase()` toggles the case of a Latin character, but doesn't affect control character.

# Answer
> 3 votes
# Jelly,  ~~38~~  37 bytes

```
“Æz⁶ɦG!€u<ʂCP]ƭƝ’œ?ØṖḟØB¤ḊØD;ṙ21,ƊyŒs

```

A monadic Link accepting a list of characters which yields a list of characters.

**Try it online!**

### How?

Forms a mapping for non alphabetic characters, applies the translate atom, `y`, and then swaps case.

```
“Æz⁶ɦG!€u<ʂCP]ƭƝ’œ?ØṖḟØB¤ḊØD;ṙ21,ƊyŒs - Link: list of characters, S
“Æz⁶ɦG!€u<ʂCP]ƭƝ’                     - base 250 number              =53994992086540427749431907521542401
                        ¤             - nilad followed by link(s) as a nilad:
                   ØṖ                 -   printable characters       = !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
                      ØB              -   base-62 characters         =0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
                     ḟ                -   filter discard             = !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
                 œ?                   - lexicographical permutation  = '=<_>?;{|}~)!@#$%^&*("+,-./:[\]`
                         Ḋ            - dequeue                      ='=<_>?;{|}~)!@#$%^&*("+,-./:[\]`
                          ØD          - digit characters             =0123456789
                            ;         - concatenate                  =0123456789'=<_>?;{|}~)!@#$%^&*("+,-./:[\]`
                                 Ɗ    - last three links as a monad:
                              21      -   twenty-one
                             ṙ        -   rotate left                =)!@#$%^&*("+,-./:[\]`0123456789'=<_>?;{|}~
                                ,     -   pair                       =)!@#$%^&*("+,-./:[\]`0123456789'=<_>?;{|}~ and 0123456789'=<_>?;{|}~)!@#$%^&*("+,-./:[\]`
                                  y   - translate (S)
                                   Œs - swap case

```

# Answer
> 2 votes
# Perl 5 `-p`, ~~92~~ 91 bytes

*-1 byte thanks to @ValueInk*

```
s/[]a-z{}|\\[]/$&^$"/gei;y/0-9)!@#$%^&*(`~\-=_+';":,.\/<>?/)!@#$%^&*(0-9~`_+\-=":';<>?,.\//

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~53~~ ~~36~~ 35 bytes

```
.šžQžiмDœ•1ĀêŽƵÆ{çIΣeÿí‚Ð"pkālrÙ•è‡

```

-1 byte implicitly thanks to *@Grimmy* due to his comment.

Try it online or verify all printable ASCII characters. NOTE: The TIO versions use the `S•...•.I` (builtin for the n'th permutation of a list) instead of `œ•...•è` (push all permutations of the string (extremely slow bottleneck for a string this large), and index into it).

**Explanation:**

```
.š        # Switch-case of the (implicit) input-character (if it's a letter)
  žQ      # Push all printable ASCII characters:
          #   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
    žiм   # Remove all letters [A-Za-z]:
          #   !"#$%&'()*+,-./0123456789:;<=>?@[\]^_`{|}~
  D       # Duplicate it
   œ      # Push a list of all permutations of this string
    •1ĀêŽƵÆ{çIΣeÿí‚Ð"pkālrÙ•
         "# Push compressed integer 540470878544692028277787799913384202055137480696656
     è    # Index it into the string-list of permutations:
          #   1'3457"908=<_>?)!@#$%^&*(;:,+./2{|}6-~[\]`
  ‡       # Transliterate the characters at the same indices
          # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•1ĀêŽƵÆ{çIΣeÿí‚Ð"pkālrÙ•` is `540470878544692028277787799913384202055137480696656`.

This number(+1) is generated by the Jelly builtin `Œ¿`, which gets the 1-based index of the permutation.

# Answer
> 2 votes
# Pure Bash, ~~170~~ 165 bytes

```
a=`echo {A..Z}`')!@#$%^&*("+,-./:[\]`'
b=`echo {a..z}`0123456789"'=<_>?;{|}~"
c=$a$b
d=$b$a
for((;n<164;n++)){ [ "$1" = "${c:n:1}" ]&&echo ${d:n:1}&&exit;}
echo "$1"

```

Try it online!

I decided to implement a solution inspired by @Noodle9's very nice answer, but using pure bash without any utilities (like tr).

Note that you need to run this in an empty directory; this can be fixed at the cost of 2 bytes by using quotes for `"{d:n:1}"`. (This issue only arises with a non-empty current directory when the input is `8`, so the output is supposed to be `*`.)

On the other hand, you can gain 2 bytes if you don't require output for the input `\n`: just eliminate the quotes in the final `echo`.

# Answer
> 2 votes
# Julia, 87 bytes

```
x->Char[0:32;b"1'3457\"908=<_>?)!@#$%^&*(;:,+./2";97:125;b"6-~";65:93;96;127][Int(x)+1]

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Extended), 60 bytesSBCS

Anonymous tacit prefix function.

```
-(,⊃⍨⍳-¯1*⍳)⍨('"''+=,<-_.>/?:;[{\|]}`~',∊')!@#$%^&*(',¨⎕D),-

```

Try it online!

`-` swap case

`(``),` prepend the following:

`⎕D` the digits

`')!@#$%^&*(',¨` prepend each of these characters to the corresponding digit

**ϵ**nlist (flatten)

`'"''+=,<-_.>/?:;[{\|]}`~',` prepend these characters (`''` is an escaped single quote)

`-(``)⍨` apply the following function with that as *left* argument and the case-swapped original argument as *right* argument:

**ɩ**ndex of the case-swapped argument in the substitution string

`¯1*` negative one raised to that power

`⍳-` subtract that from the **ɩ**ndex of the case-swapped argument in the substitution string

`,⊃⍨` use that to pick an element from the case-swapped argument appended to the substitution string

# Answer
> 1 votes
# Pure Bash, 217 bytes

```
P=printf\
a=`$P%x "'$1"`
case $a in 3[ab])x=1;;2[27])x=5;;2[68]|3[79])x=17;;2a|38)x=18;;2b|3d)x=22;;29|30)x=25;;36|5e)x=104;;2d|32|40|5f)x=114;;20|7f)x=0;;60|7e)x=30;;[23]?)x=16;;[4-7]?)x=32
esac
$P\\`$P%o $[0x$a^x]`

```

Try it online!

Just bash -- no Unix utilities.

Input character is passed as an argument, and the output is on stdout.

**\_____________________________________________________________**

**Test runs:**

```
$ cat shifttoggle
P=printf\
a=`$P%x "'$1"`
case $a in 3[ab])x=1;;2[27])x=5;;2[68]|3[79])x=17;;2a|38)x=18;;2b|3d)x=22;;29|30)x=25;;36|5e)x=104;;2d|32|40|5f)x=114;;20|7f)x=0;;60|7e)x=30;;[23]?)x=16;;[4-7]?)x=32
esac
$P\\`$P%o $[0x$a^x]`

$cat shifttoggleTest
#!/bin/bash

count=1

for s in ')!@#$%^&*("+,-./:' "0123456789'=<_>?;" ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz '[\]`' '{|}~' $' \a\n\r\t\x7F\x80\x88\x8F'
  do
    echo "TEST #$count"

    for ((n=0;n<${#s};n++))
      do
        c="${s:$n:1}"
        d=`./shifttoggle "$c"`

    # Backticks remove any trailing newline, so restore that here for the case where c is \n (you can check that shifttoggle really prints \n in that case).
    if test -z "$d"
          then
            d=$'\n'
        fi

    if test "$count" -eq 7
          then
            printf "  ASCII %d => ASCII %d\n" "'$c" "'$d"
      else
            echo "  $c => $d"
        fi

      done

      (( count++ ))
      echo ''
  done

$ ./shifttoggleTest
TEST #1
  ) => 0
  ! => 1
  @ => 2
  # => 3
  $ => 4
  % => 5
  ^ => 6
  & => 7
  * => 8
  ( => 9
  " => '
  + => =
  , => <
  - => _
  . => >
  / => ?
  : => ;

TEST #2
  0 => )
  1 => !
  2 => @
  3 => #
  4 => $
  5 => %
  6 => ^
  7 => &
  8 => *
  9 => (
  ' => "
  = => +
  < => ,
  _ => -
  > => .
  ? => /
  ; => :

TEST #3
  A => a
  B => b
  C => c
  D => d
  E => e
  F => f
  G => g
  H => h
  I => i
  J => j
  K => k
  L => l
  M => m
  N => n
  O => o
  P => p
  Q => q
  R => r
  S => s
  T => t
  U => u
  V => v
  W => w
  X => x
  Y => y
  Z => z

TEST #4
  a => A
  b => B
  c => C
  d => D
  e => E
  f => F
  g => G
  h => H
  i => I
  j => J
  k => K
  l => L
  m => M
  n => N
  o => O
  p => P
  q => Q
  r => R
  s => S
  t => T
  u => U
  v => V
  w => W
  x => X
  y => Y
  z => Z

TEST #5
  [ => {
  \ => |
  ] => }
  ` => ~

TEST #6
  { => [
  | => \
  } => ]
  ~ => `

TEST #7
  ASCII 32 => ASCII 32
  ASCII 7 => ASCII 7
  ASCII 10 => ASCII 10
  ASCII 13 => ASCII 13
  ASCII 9 => ASCII 9
  ASCII 127 => ASCII 127
  ASCII 128 => ASCII 128
  ASCII 136 => ASCII 136
  ASCII 143 => ASCII 143

```

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

```
char*strchrnul(),*s=")0@2^6&7*8(9\"'+=-_:;`~\0";f(c){c=s[strchrnul(s,c)-s^1]?:(c%127>32)<<4+c/64^c;}

```

Similar to the Javascript strategy. I'd like to get rid of the extra parentheses but this is pretty good.

Try it online!

# Answer
> 1 votes
# Ruby `-p`, 66 bytes

Builds the "lowercase" and "uppercase" strings so that everything lines up, and connects them together to be passed into the `tr` function so it can do the proper conversions.

```
l="\\-a-z0-9=[-];',./`"
u='_A-Z)!@#$%^&*(+{|}:"<>?~'
$_.tr!u+l,l+u

```

Try it online!

# Answer
> 1 votes
# PowerShell, 189 bytes

```
param($x)if(($s=")0@2^6&7*8(9""'+=-_:;``~").contains($x)){$s[$s.indexof($x)-bxor1]}else{
$n=[byte][char]$x;if($n-in32..64){[char]($n-bxor16)}elseif($n-in65..127){[char]($n-bxor32)}else{$x}}

```

Try it online!

# Answer
> 1 votes
# PowerShell, 111 bytes

```
$k=')!@#$%^&*("+,-./:[\]`'+'A'..'Z'+"0123456789'=<_>?;{|}~"+'a'..'z'
"$k$k$args"[($p=$k|% i*f @args)+72*!!++$p]

```

Try it online!

`i*f` is shortcut for `indexOf`.

Explain:

* The shift series contains 72 chars `)!@#..A B C.. Y Z`.
* The shift-ness series contains 72 chars also
* `$k` contains concatenated shift and shift-ness series
* if `$args` does not found in `$k`, then `indexOf` returns `-1` and script returns the last char from string `$k+$k+$args`. It is `$args`.
* if `$args` found in `$k`, then the script return shifted char.

---
Tags: code-golf, keyboard
---


title: Random pair of primes

text:
# Question
Title: Random pair of primes
Given a positive input \\$n\\$, output a random pair of primes whose difference is \\$n\\$. It's fine if there's another prime between them.

Every pair should possibly appear and the program should have zero possibility to fall into infinite loop.

It's promised that such pair exist, but not always infinite, so beware. You also shouldn't assume it's infinite for even \\$n\\$ until a proof exist.

Test cases:

```
2 -> [3,5], [11,13], [29,31], etc.
3 -> [2,5]
4 -> [3,7], [19,23], etc.
7 -> Undefined behavior

```

Shortest code win.

# Answer
# 05AB1E, 13 bytes

Generates a random integer \\$k\\$ until both \\$k\\$ and \\$k+n\\$ are prime.

```
[Î‚[>₄Ω#}DpP#

```

Try it online! Runs the program 1000 times and shows the unique results.

**Commented:**

```
[              # loop:
 Î‚            # push [0, input]
   [    }      # loop:
    >          #   increment both integers
     ₄Ω        #   draw a random digit of 1000
       #       #   if this is 1, stop the loop
         D     # duplicate the current pair
          p    # for both integers: are they prime?
           P   # take the product
            #  # if both are prime, end the main loop

```

---

Old answer that always just generates one random integer, 22 bytes:

```
∞+∞ø.ΔpP}D[₄Ω#>}DpP_i\

```

Try it online! Runs the program 100 times to demonstrate different outputs.

`∞+∞ø.ΔpP}` finds the first valid pair.
`[₄Ω#>}` is a loops which increments the pair and has a \\$50\\%\\$ probability to stop at every iteration.
`DpP_i\` removes the new pair if any of the numbers is not prime.
> 7 votes

# Answer
# , ~~111~~ ~~105~~ ~~103~~ ~~73~~ ~~70~~ 69 bytes

*Edit: -2 bytes thanks to Robin Ryder (as well as -5 more bytes for the now-discarded previous version)*

```
function(s){while(sum(!(z=T+s*0:1)%%rep(2:T,e=2))>1)T=1+rpois(1,9)
z}

```

Try it online!

Picks random numbers `n` until (`n`,`n+s`) are both prime.
> 7 votes

# Answer
# Haskell, ~~132~~ 130 bytes

```
f$[2..]>>= \x->[2..x]
f(x:y)n=do b<-randomIO;last$f y n:[pure(x,x+n)|b,p x,p$x+n]
p n=all((>0).mod n)[2..n-1]
import System.Random

```

Try it online!

The relevant function is `f$[2..]>>= \x->[2..x]`, which takes `n` as input and returns a random pair of primes `(x,x+n)`.

Definitely not the shortest possible answer, but what I like about it is that, when given enough time, it will actually generate *every* possible pair of primes at distance \\$n\\$, no matter how large. Also, unlike my two other answers below, it has the nice advantage of actually taking less than a googol years to produce some output.

## How?

The idea is to iterate over the list

```
[2..]>>= \x->[2..x]≡[2,2,3,2,3,4,2,3,4,5,2,3,4,5,6,2,3,4,5,6,7,...]

```

which contains every integer \\$\ge 2\\$ infinitely many times. Whenever we encounter a number \\$x\\$ such that \\$x\\$ and \\$x+n\\$ are prime, we output the pair \\$(x,x+n)\\$ with probability \\$\frac{1}{2}\\$ (`b<-randomIO` picks a `Bool` at random), otherwise we keep going. The program will halt with probability \\$1\\$, however the probability of outputting anything other than the first pair is *very* low, especially for larger values of \\$n\\$. The TIO link above runs the function \\$1,\\!000,\\!000\\$ times, and collect the unique results.

# Haskell, ~~115~~ ~~102~~ 104 bytes

```
f n=do x<-randomIO;last$f n:[pure(x,x+n)|x>1,p x,p$x+n]
p n=all((>0).mod n)[2..n-1]
import System.Random

```

Try it online!

The relevant function here is `f`.

This code will *almost never* run in a reasonable amount of time, but theoretically, if given enough time, it should output all the prime pairs \\$(x,x+n)\\$ with \\$x\<2^{63}\\$ (the `System.Random` random generator can't generate numbers larger than this).

## How?

This is the naive approach: generate a random number \\$x\\$, check if \\$x\\$ and \\$x+n\\$ are prime, and in this case return \\$(x,x+n)\\$. Otherwise try again.

# Haskell, 117 bytes

```
(2?)
x?n=do d<-randomIO;last$(x+d)?n:[pure(x,x+n)|d>0,x>1,p x,p$x+n]
p n=all((>0).mod n)[2..n-1]
import System.Random

```

Try it online!

The relevant function is `(2?)`.

A mix of the two solutions above. It has the theoretical guarantees of the first (given enough time, it should generate all the prime pairs with difference \\$n\\$, even if the primes are larger than \\$2^{63}\\$). However, the probability of generating some output within a reasonable amount of time is close to \\$0\\$, except if \\$(2+n)\\$ is prime.

## How?

Start with `x=2`. If `x` and `x+n` are both primes, then return `(x,x+n)` with probability \\$\frac{1}{2}\\$. Otherwise, add a random number `d` (which can be positive or negative) to `x` and repeat.
> 6 votes

# Answer
# MATL, ~~16~~ 15 bytes

```
`,1r/kYq]-G-}2M

```

Outputs the two primes in decreasing order. **Try it online!**

### Explanation

Let \\$q(k)\\$ denote the \\$k\\$-th prime: \\$q(1)=2\\$, \\$q(2)=3\\$, \\$q(3)=5\\$, \\$\ldots\\$

The code generates two random primes \\$r\_1, r\_2\\$ independently with distribution

\\$\quad \displaystyle \Pr\[r\_i = q(k)\] = \frac 1 {k\cdot(k+1)}; \quad i = 1,2; \quad k = 1,2,3,\ldots\\$

The distribution of \\$k\\$ is easily obtained as the inverse of a normalized uniform random variable rounded down. Each pair of primes has nonzero probability of occuring.

If the two generated primes happen to differ by the input \\$n\\$, they are displayed and the program ends. Else the process is repeated.

```
`        % Do while
  ,      %   Do twice
    1    %     Push 1
    r    %     Push random number between 0 and 1
    /    %     Divide
    k    %     Round down. Gives a random positive integer, k
    Yq   %     k-th prime
  ]      %   End
  -      %   Subtract. Gives the difference between the two primes (*)
  G      %   Push program input, n
  -      %   Subtract. (This will used as the loop condition) (**)
}        % Finally (execute on loop exit)
  2M     %   Push inputs to second-to-last normal function (*): latest two primes
         % End (implicit). A new iteration will be run if (**) is nonzero
         % Display stack (implicit)

```
> 3 votes

# Answer
# Husk, 15 bytes

```
ḟΛṗmoSe+⁰L↓x1İπ

```

Try it online!

**Note: requires input of a random 'seed' to generate different output on different runs**

Husk is completely deterministic, and has no built-in random number generator. However, some googling indicates that the digits of Pi have been shown to be 'random' (in a certain statistical sense), if a set of constraints about the distribution of chaotic sequences holds true (1). Although this conjecture is still unproven, it suggests that we can use the digits of Pi as the basis for a random number generator, until proven otherwise (2).

Obviously, Pi is constant, so we will need to 'seed' the random number generator if we wish to obtain different results for successive runs of the program. However, one could argue that this is not substantially different from the 'seeding' of other pseudo-random number generators in other programming languages.

So: our Pi-based random number generator (`mL↓x1İπ`: try it!) outputs the separation between occurrences of the digit `1` in the decimal representation of Pi, after skipping the first `s` outputted numbers with `s` given as the 'seed'. I believe that this series should include all non-negative integers with non-zero frequency. Please correct me if I'm wrong!

With that out of the way, here's the 'random pair of primes' program, which simply outputs the first pair it finds of randomly-picked numbers with spacing `n` that are both primes:

```
             İπ     # Get the (decimal) digits of pi as an infinite list;
           x1       # split into sublists on every occurrence of the digit '1';
          ↓         # discard as many initial sublists as the random 'seed';
         L          # and get the length of each sublist:
                    # this is our random sequence.
   moSe             # Now, for each random number, make a 2-element list
       +⁰           # by combining with itself plus the input value of 'n';
ḟ                   # and output the first 2-element list that satisfies:
 Λṗ                 # both elements are primes.

```

This link tests `n=4` for random seeds of 1..100 to confirm that various different outputs can be obtained when there is more-than-one solution;
This link tests `n=3` for random seeds of 1..100 to confirm that when there is only one solution, this is always outputted.

(1) https://www.nersc.gov/news-publications/nersc-news/science-news/2001/are-the-digits-of-pi-random/
(2) And if that's not Ok, then this is probably not Ok either: https://codegolf.stackexchange.com/a/223136/95126
> 2 votes

# Answer
# APL (Dyalog Unicode), 40 bytes

```
{⍵{⍵[⊃(?∘⍴⌷⊢)⍸⍺=-∘.-⍨⍵]}(⊢~∘.×⍨)1↓⍳3300}

```

Not entirely certain that I understood the problem statement. I run out of memory with primes larger than around 3300. Not great, but it's my first stab at it.

```
⍵{...} ⍝ passing user input to nested function as left argument
  ⍵[...] ⍝ retrieving primes for given index values
    ⊃(?∘⍴⌷⊢) ⍝ randomly selecting pair of primes from list
      ⍸⍺= ⍝ index value of every difference equal to the user input n
        - ⍝ negation
          ∘.-⍨⍵ ⍝ matrix of all possible differences between primes
            (⊢~∘.×⍨) ⍝ list of primes in range (inclusive) found by not being members of the composite matrix (created by outer product)
              1↓⍳3300 ⍝ range 2–3300 (determined by tio memory limit, though TryAPL allowed for double that)

```

Try it online!
> 1 votes

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

```
f=n=>(g=d=>k%--d?g(d):d>1)(k=2/Math.random()|0)|g(k+=n)?f(n):[k-n,k]

```

Try it online!

Still shorter than Arnauld's wrong answer
> 0 votes

# Answer
# Jelly,  ~~16~~  15 bytes

```
2‘XḂ$¿,³Ä¹ßẒẠ$?

```

A full program that prints a random, valid pair - if given enough time and recursion stack/memory (recursion depth is set to \\$2^{30}\\$ in TIOs interpreter/Dennis' GitHub; but we seg-fault before then generally).

**Try it online!** Note that there is a seg-fault for high `n` (or always for those invalid `n` which are odd while `n+2` is not prime).

### How?

Chooses a random integer greater than 1, pairs it with the integer that's `n` greater. Then, if both are prime stops and outputs, otherwise repeats the whole procedure again.

The procedure for choosing a random integer, while golfy, will find low numbers exponentially more often than high numbers, so the lowest possible pair is produced extremely often with even modest n.

```
2‘XḂ$¿,³Ä¹ßẒẠ$? - Main Link - called with 1 program argument, n
2               - set the left argument, say v, to two
     ¿          - while...
    $           - ...this is true: last two links as a monad - f(v):
  X             -   random integer in [1,v]
   Ḃ            -   is odd?
 ‘              - ...do: increment
      ,³        - pair with n -> [v, n]
        Ä       - cumulative sums -> [v, n + v]
              ? - if...
             $  - ...condition:
           Ẓ    -   is prime (vectorises)
            Ạ   -   all?
         ¹      - ...then: no-op
          ß     - ...else: call Main Link again
               - implicit print

```
> 0 votes

# Answer
# Japt, 25 bytes

**Warning:** This **will** hang your browser if the random value is unfavorable. It does however not have an infinite loop, just a very, very long runtime in bad cases.

This relies on the given assumption that a satisfactory pair is guaranteed to exist. Starting from a random whole number ensures that any pair can be returned, after that we just move -1, +1, -2, +2 etc until we find a number that satisfies the input.

```
@T=[X,X+U];Tej}c(1/Mr)c;T
                (1/Mr)c   // Starting from a random whole number,
@             }c          // try that number -1, +1, -2, +2 etc until we find one where
 T=[X,X+U];               // that number as well as that number plus input
           Tej            // are both prime.
                       ;T // Return the resulting array.

```

Try it here.
> 0 votes

# Answer
# Japt, ~~14~~ 13 bytes

Takes input as a single integer array. Weighted very heavily towards the earlier pairs in the sequence.

```
iT Èej}a@m+Xö

```

Try it
> 0 votes

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


title: Knight's tour on a rectangle

text:
# Question
Title: Knight's tour on a rectangle
Given an a-by-b sized grid, and a chess knight, determine:

* A starting point and path the knight can take to visit every square in the grid
* or "NOT POSSIBLE", if not possible.

**Input:** Two integers, `a`, `b`.

**Output:** Numbers output in an a-by-b grid:

```
1 4 7 10
8 11 2 5
3 6 9 12

```

Where `1` is where the knight starts, `a*b` is where the knight ends, and the numbers signify the path the knight must take, in ascending order. The knight cannot land on the same square twice.

The rows of the grid must be separated with a newline, and the items in each row must be separated with a space.

**Test Cases:**
| is a newline.
`3 4 -> 1 4 7 10 | 8 11 2 5 | 3 6 9 12`
`2 3 -> NOT POSSIBLE`

If there is a solution there will be more than one: any valid solution is acceptable.

Shortest code wins. **Please do not use any programming languages that are known to produce short programs: e.x. GolfScript, APL, J, K, etc.**

# Answer
> 4 votes
### Ruby, 306 284 characters

```
w,h=eval"[#{gets}]"
f=Hash.new{|g,k|s,x,y,*r=k
x<0||y<0||x<w&&y<h&&s>0&&'$&(,268:'.bytes{|u|r|=f[[s-1,x-2+u%5,y-9+u/5]].select{|l|l[y*w+x]<1}}
g[k]=r.map{|l|l=l*1;l[y*w+x]=s;l}}
f[[1,0,0]]=[[1]+[0]*(w*h-1)]
(s=f[[w*h,w-1,h-1]][0]||(puts"NOT POSSIBLE"))&&s.each_slice(w){|f|puts f*" "}

```

Implementation in Ruby, takes input from STDIN and outputs to STDOUT. Although a little bit optimized it is still extremely slow on large grids.

```
> 5,3
NOT POSSIBLE

> 5,4
1 18 5 12 9
6 15 10 19 4
17 2 13 8 11
14 7 16 3 20

```

*Edit:* Ventero pointed out some improvements whiche saved several chars. I also changed the encoding of possible moves to be much shorter now.

# Answer
> 3 votes
## Python, 420

```
w,h=input()
s=w*h
d=range
def r(l):y=l/w;x=l%w;return[x+p+w*(q+y)for p,q in[(1,2),(2,1),(-2,1),(-1,2),(-1,-2),(-2,-1),(2,-1),(1,-2)]if 0<=x+p<w and 0<=q+y<h]
def f(p):
 a={l:len(r(l))for l in r(p[-1])if l not in p}
 for l in[k for k in a if a[k]==min(a.values())]:
    x=f(p+[l])
    if len(x)==s:return x
 return p
e=f([0])
print len(e)<s and"NOT POSSIBLE"or'\n'.join([' '.join(`e.index(x+y*w)+1`for x in d(w))for y in d(h)])

```

I've sacrificed shorter code for reasonable performance, so it should be able to find solutions for boards up to 9x9 in under 3 seconds.

# Answer
> 1 votes
### C# ~~796~~ 793

```
using System;using System.Collections.Generic;using System.Linq;namespace Z{public class P{public static void Main(){new P().K(3,4);}int x, y;void K(int a, int b){x=a;y=b;for(var s=0;s<x*y;s++)K(new[]{s});Console.WriteLine("NOT POSSIBLE");}void K(int[] v){if(v.Length<x*y)foreach(var m in M(v))K(v.Concat(new[]{m}).ToArray());else{Console.WriteLine(String.Join("\n",v.Select((p,i)=>new{p,i}).OrderBy(e=>e.p).GroupBy(e=>e.p/y).Select(g=>String.Join(" ",g.Select(e=>e.i+1)))));Environment.Exit(0);}}IEnumerable<int> M(int[] v){var c=v.Last();var q=new{X=c/y,Y=c%y};return(from m in new[]{new{X=1,Y=2},new{X=2,Y=1}}from d in Enumerable.Range(0,4).Select(i=>new{X=(i&2)-1,Y=(i&1)*2-1})select new{X=q.X+d.X*m.X,Y=q.Y+d.Y*m.Y}into p where p.X>=0&&p.Y>=0&&p.X<x&&p.Y<y select p.X*y+p.Y).Except(v);}}}

```

This code finds a solution (if any) using brute force. Here's the ungolfed (and slightly refactored) version: http://pastie.org/4149829

**Input:** Modify the parameters in the `new P().K(...);` call.

**Output:** To the console, in the required format

**Online demos:**

Test Case 1 (3, 4): http://ideone.com/UU9sw (another solution than OP's, but it's a valid one)

Test Case 2 (2, 3): http://ideone.com/ZX9xC

A bigger board (4, 7): http://ideone.com/QKuXL *(this takes close to 5s to run, so retry if it fails the first time)*.

***Note:** Mono does not have the `String.Join` method overload that takes as a parameter an `IEnumerable<T>`, so in order to get this working on IdeOne I have to modify the code a bit (modify these `IEnumerable<T>`s to `string[]`).*

# Answer
> 1 votes
### Ruby ~~364~~ 359

```
K=->a,b{A,B=a,b;(0...A*B).each{|i|Z[[i]]};p"NOT POSSIBLE"}
Z=->v{c=v.last
abort (0...v.size).map{|i|{:i=>i+1,:x=>v[i]}}.sort_by{|i|i[:x]}.map{|i|i[:i]}.each_slice(B).map{|r|r*' '}*?\n if v.size==A*B
([[1,2],[2,1],[-2,1],[-1,2],[-1,-2],[-2,-1],[2,-1],[1,-2]].map{|d|o=(c/B)+d[0]
u=(c%B)+d[1]
(o>=0&&0<=u&&A>o&&B>u)?o*B+u :-1}.flatten-[-1]-v).each{|i|Z[v+[i]]}}

```

Same idea as my C# answer.

This gets invoked like this: `K[a,b]` and outputs the desired result to the console.

**Online demos:**

Test case 1: http://ideone.com/yDiiS

Test case 2: http://ideone.com/WVUmX

Example of a bigger board (4x5): http://ideone.com/hItNo

# Answer
> 1 votes
# Python, 316

Took about 30 minutes to run on input of `3 4`. I wouldn't try it on anything larger.

```
import itertools as I
r=range
x,y=map(int,raw_input().split())
m=[(a,b)for a in r(x)for b in r(y)]
q=[n for n in I.permutations(m,x*y)if all((abs(o[0]-p[0]),abs(o[1]-p[1]))in((1,2),(2,1))for(o,p)in zip(n,n[1:]))]
print'\n'.join(' '.join([`q[0].index(z)+1`for z in m][i:i+y])for i in r(0,x*y,y))if q else"NOT POSSIBLE"

```

I notice the other Python answers get input by doing `x,y=input()` rather than `x,y=map(int,raw_input().split())`, but the question does not allow for commas in the input so it seems the former method would fail. If the question does allow commas in the input, I'll shave an additional 20 characters off my answer.

I tried a recursive solution, but the best I could get was 334 characters:

```
r=range
x,y=map(int,raw_input().split())
m=[(a,b)for a in r(x)for b in r(y)]
o=[]
def f(m,x=0):
 for n in m:
  if x==0 or map(lambda x,y:abs(x-y),n,x)in([1,2],[2,1])and not o:
   if len(m)==1 or f(m-{n},n)or o:o.append(n)
f(set(m))
print'\n'.join(' '.join([`o.index(z)+1`for z in m][i:i+y])for i in r(0,x*y,y))if o else"NOT POSSIBLE"

```

# Answer
> 0 votes
## VBA 494 574 833 chars

Fixing to account for the transposed example added quite a bit of code...

I squeezed a little more out be shifting around some `If` checks to avoid using `End If`.

This now correctly handles `4, 5` and `5, 4`, but it takes impossibly long for `4, 7`, and I'm not 100% sure it works for that set.

```
Dim z,v,e,i,j,p,l
Sub k(a,b)
e=a*b:q:i=2
If c(a,b) Then z(e)=e:j=e+1
For i=1 To e:s=s & z(i) & IIf(i Mod b=0,vbCr,vbTab):Next
MsgBox IIf(j-1=e,s,"NOT POSSIBLE")
End Sub
Sub o()
z(l)=j:v(l)=1:p=l:i=p:j=j+1
End Sub
Sub u(r,t)
z(r)=0:v(r)=0:p=t:j=j-1
End Sub
Sub q()
ReDim z(1 To e),v(1 To e):z(e)=e:v(e)=1:p=1:z(1)=p:v(1)=p:j=2
End Sub
Function w(b)
f=(p-1) Mod b+1:m=(l-1) Mod b+1:g=Int((p-1)/b)+1:n=Int((l-1)/b)+1:w=(((f-2=m Or f+2=m) And (g-1=n Or g+1=n)) Or ((f-1=m Or f+1=m) And (g-2=n Or g+2=n)))
End Function
Function c(a,b)
t=p:m=i:
If i>1 And i<e Then
For h=1 To 8:l=p+Choose(h,(b-2),(b+2),(2*b-1),(2*b+1),-(b-2),-(b+2),-(2*b-1),-(2*b+1)):r=l:If l>1 And l<e Then If v(l)=0 Then If w(b) Then o:If j>=e Then l=j:If w(b) Then c=1 Else u r,t Else c=c(a,b):If c=0 Then u r,t
Next:End If
If c=(i>=e) Then i=m+1:c=c(a,b)
End Function

```

# Answer
> 0 votes
## Python, 370 367 366 338

Simple recursive solution. It isn't efficient, but works fast for example cases :-)

```
import itertools as I
P=I.product
a,b=input()
r=range;A=r(a);B=r(b);T={}
def S(x,y):
 if 0<=x<a and 0<=y<b and(x,y)not in T:
    T[x,y]=len(T)+1
    for i,j in P((-2,2),(-1,1)):S(x+i,y+j);S(x+j,y+i)
    if len(T)!=a*b:T.pop((x,y))
for q,w in P(A,B):S(q,w)
print"\n".join(" ".join(str(T[i,j])for j in B)for i in A)if len(T)==a*b else'NOT POSSIBLE'

```

# Answer
> 0 votes
# APL (Dyalog Extended), 22 bytes (SBCS)

```
⊃⌂kt,⍥⊆'NOT POSSIBLE'⍨

```

Try it online!

the first of…

`⌂kt` the first knights tour (if possible, else: an empty list)

`,⍥⊂` juxtaposed with

`'NOT POSSIBLE'⍨` the required fall-back value

---
Tags: code-golf, chess
---


title: Multiplicative Persistence #2

text:
# Question
Title: Multiplicative Persistence #2
We had a challenge on Multiplicative Persistence here.
As a recap, to get a multiplicative persistence of a number, do these steps:

1. Multiply all the digits of a number (in base \\$10\\$)
2. Repeat Step 1 until you have a single digit left.
3. Then count the number of iterations.

More here on *Numberphile*:

See the previous challenge.

# Rules

The last challenge was all about seeing the intermediate results, but here:

* The input should be a positive integer \\$n\\$.
* The output should be the integer with the greatest multiplicative persistence among numbers from \\$0\\$ to \\$n-1\\$, choosing the smallest option in case of a tie.
* This is , so the shortest code wins.

# Example

```
[inp]: 10
[out]: 0

[inp]: 100
[out]: 77

[inp]: 50
[out]: 39

[inp]: 31
[out]: 25

```

Note: Numbers *somewhat* randomly chosen.

Good Luck!

# Answer
# Husk, 10 bytes

```
►ȯLU¡oΠd↔ŀ

```

Try it online!

## Explanation

```
►ȯLU¡oΠd↔ŀ
        ↔ŀ reverse the range 0..n-1
►ȯ         max-by, returning the last maximal element for the following:
    ¡o      create an infinite list using:
      Πd     product of digits.
   U        longest unique prefix
  L         take its length

```
> 8 votes

# Answer
# Jelly, 10 bytes

```
ḶDP$ƬL$ÐṀḢ

```

Try it online!

# Jelly, 10 bytes

```
ḶDP$Ƭ€ẈMḢ’

```

Try it online!

## How they work

```
ḶDP$ƬL$ÐṀḢ - Main link. Takes n on the left
Ḷ          - Unlength; [0, 1, 2, ..., n-1]
      $ÐṀ  - Return the maximal elements under the previous 2 links:
   $Ƭ      -   Iterate the previous 2 links until reaching a fixed point, collecting all steps:
 D         -     Digits
  P        -     Product
     L     -   Length; Number of steps
         Ḣ - Take the lowest maximal element

```

```
ḶDP$Ƭ€ẈMḢ’ - Main link. Takes n on the left
Ḷ          - Unlength; [0, 1, 2, ..., n-1]
     €     - Over each integer, 0 ≤ i < n:
   $Ƭ      -   Iterate the previous 2 links until reaching a fixed point, collecting all steps:
 D         -     Digits
  P        -     Product
      Ẉ    - Lengths of each
       M   - 1-indices of maximal elements
        Ḣ  - Take the first (lowest) one
         ’ - Decrement to 0-index

```
> 6 votes

# Answer
# , ~~94~~ ~~91~~ 87 bytes

*Edit: thanks to Kirill L. for spotting 2 (!) bugs, and also saving 3 bytes, and -4 more bytes thanks to Robin Ryder*

```
which.max(Map(f<-function(x)`if`(x>9,1+f(prod(utf8ToInt(c(x,""))-48)),0),1:scan()-1))-1

```

Try it online!

Started as a rather unimaginative construction based around Giuseppe's 'Multiplicative persistence' answer, which deserves most of the credit.

Now adjusted (in response to bug-spotting by Kirill L.) into a recursive version that saved all the bytes needed for the bug-fix (I hope)...
> 6 votes

# Answer
# Julia 0.7, ~~58~~ ~~54~~ 49 bytes

```
n->argmax(.!(0:n-1))-1
!n=n>9&&!prod(digits(n))+1

```

Try it online!

Thanks to MarcMush for -5 bytes.
> 6 votes

# Answer
# Python 2, 70 bytes

```
lambda n:max(range(n),key=g)
g=lambda x:x<10or-~g(eval('*'.join(`x`)))

```

Try it online!

The helper function `g` recursively computes multiplicative persistence, and the main function in the top line finds value that maximizes `g` among the half-open range from `0` to `n`. It works out that `max` chooses the earlier element in case of a tie for greatest.
> 6 votes

# Answer
# 05AB1E, 12 bytes

```
L<ε.ΓSP}g]Zk

```

Try it online!

**Commented:**

```
L<           # push [1 .. input] - 1
  ε      }   # map over each integer:
   .Γ  }     #   cumulative fixed-point:
             #     run until the result doesn't change and collect results
     SP      #     take the product (P) of the digits (S)
        g    #   get the length of the resulting list
          Zk # find the index (k) of the minimum length (Z)

```

Alternative 12 byters: `FN.ΓSP])€gZk` and `<1ŸΣ.ΓSP}g}θ`
> 4 votes

# Answer
# JavaScript (ES6), 77 bytes

```
f=(n,m)=>n--?f(n,m>(g=n=>v=n>9&&-~g(eval([...n+''].join`*`)))(n)?m:(x=n,v)):x

```

Try it online!
> 4 votes

# Answer
# Vyxal , 9 bytes

```
ƛ⁽Π↔L;:Gḟ

```

Try it Online!

Never have I had to use both `m` and `M` flags in the same challenge.

## Explained

```
ƛ⁽Π↔L;:Gḟ
ƛ         # over the range [0, input) - managed by the m and M flags
 ⁽Π↔      #     get the iterations of the multiplicative persistance - repeatedly take the product of the digits of each number in the range, collecting results until it doesn't change
    L;    #     and take the length
      :G  # push the maximum element and
        ḟ # get the first index where it occurs

```
> 4 votes

# Answer
# PowerShell, 110 bytes

```
param($n)filter f{$_
if($_-gt9){("$_"|% t*y)-join'*'|iex|f}}
($k=0..$n|%{($_|f).count}).indexof(($k|sort)[-1])

```

Try it online!

Thanks to @mazzy for the function and -24 bytes
> 4 votes

# Answer
# Charcoal, 18 bytes

```
ＦＮ⊞υ∧›ι⁹⊕§υΠιＩ⌕υ⌈υ

```

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

```
ＦＮ

```

Loop over the range `0..n-1`.

```
⊞υ

```

Push to the predefined list...

```
∧›ι⁹

```

... zero if the current index is less than 10, otherwise...

```
⊕§υΠι

```

... increment the previously calculated persistence of the digital product of the current index.

```
Ｉ⌕υ⌈υ

```

Print the first entry with maximal persistence.
> 4 votes

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

```
g=n=>n>9&&-~g(eval([...n+''].join`*`));f=n=>n--?g(h=f(n))<g(n)?n:h:0

```

Try it online!
> 4 votes

# Answer
# Befunge-98 (FBBI), ~~107~~ ~~105~~ 108 bytes

+3 for a bugfix with the tiebreaks.

Definitely some golfing left to do...

```
<   v:-1_;# $ <;v#:&
e:p1 9;j`N'  <^;#1p4
;\0:<v; +1:$<^
+\1\v>:9`! #^_\1
>$$  ^      @.N'<
^#::<X'*%ap55/a_

```

Try it online! The code contains two null bytes, indicated by `N` above

### How?

slightly outdated

**Product of the digits:**
Accessing more than the top two values on the stack is quite hard in Befunge, which is why we save the remaining digits in the cell where the `X` is initially in.
`1\` inserts a 1 (initial product) below the input value, then the product is calculated by repeatedly multiplying with last digit of the remaining input.

**Computing the multiplicative persistence:**
`0\` inserts the initial value of `0` below the input integer. `:9`! #^_` continues east to increment the persistence and calculate the next product of digits as long as the top of the stack is larger than `9`, and exits to the top at `^` once a value less or equal to `9` is reached.
For a more compact version of this which prints the intermediate results, see my answer to the other challenge.

**Storing intermediate results:**
The highest persistence gets stored at the `N` at index `1, 9`, and this is directly used to be compared with new results. If the new results is not larger than the current record `;` skips the update code `91p:d4p`, which updates the record and stores the record index at `4, 13`.

**The main loop:**
The loop counts down to `0` and sends the IP off to the other code in between. Once `0` has gone around the loop, the value stored at `4, 13` is printed and the program exits.
> 4 votes

# Answer
# Scratch, 454 bytes

Try it online!

This one was fun to make! It takes 13 seconds to process the first 100,000 numbers. Alternatively, 48 blocks.

```
when gf clicked
set[H v]to(
set[M v]to(
set[N v]to(-1
ask()and wait
repeat(answer
change(N)by(1
set[C v]to(
delete all of[B v
repeat(length of(N
change[C v]by(1
add(letter(C)of(N))to[B v
end
set[P v]to(
repeat until<(length of[B v])=(1
set[R v]to(1
repeat(length of[B v
set[R v]to((R)*(item(1)of[B v
delete(1)of[B v
end
set[C v]to(
repeat(length of(R
change[C v]by(1
add(letter(C)of(R))to[B v
end
change[P v]by(1
if<(P)>(H)>then
set[H v]to(P
set[M v]to(N

```
> 4 votes

# Answer
# Python 2, 85 bytes

```
d=[]
for x in range(input()):d+=x<10or-~d[eval('*'.join(`x`))],
print d.index(max(d))

```

Try it online!

Using a function to calculate the persistence came in at 87 bytes, but there might be way to do everything in a single function.
> 3 votes

# Answer
# Haskell, ~~86~~ ~~85~~ 84 bytes

* -1 byte thanks to xnor for removing the `f 1=0` case.

```
f n|n>1,x<-f$n-1,p x>=p(n-1)=x
f n=n-1
p n|n>9=1+p(product$read.pure<$>show n)
p n=1

```

Try it online!
> 3 votes

# Answer
# Retina, 60 bytes

```
.+
*
L$`.
$.`
+/\d.+/_~(`.
$&$*
)`^
.+¶#$$.(
.
#
D`#+
¶*$

¶

```

Try it online! Link includes test cases. Explanation:

```
.+
*
L$`.
$.`

```

List the numbers up to `n`.

```
+/\d.+/_

```

Repeat while there are numbers of at least two digits...

```
~(`.
$&$*
)`^
.+¶#$$.(

```

... convert the numbers into Retina expressions that calculate their digital product and evaluate them. (As in my Retina answer to the previous challenge, an ungrouped version is actually a byte longer.)

```
.
#
D`#+

```

Keep only the the new record multiplicative persistences.

```
¶*$

¶

```

Retrieve the value with the highest new record persistence.
> 3 votes

# Answer
# Haskell, 82 bytes

```
f n=snd$minimum$((,)=<<p)<$>[0..n-1]
p n|n>9=p(product$read.pure<$>show n)-1
p n=0

```

Try it online!

Golfing Delfad0r's solution by using the decorate-sort-undecorate idiom to find the maximizing value.

It's easier to see how it works in this slightly longer version.

**83 bytes**

```
f n=snd$minimum[(-p i,i)|i<-[0..n-1]]
p n|n>9=1+p(product$read.pure<$>show n)
p n=1

```

Try it online!

For each candidate value `i`, we create the pair `(-p i,i)`, take the minimum of all of them which compares first by `-p i`, the call `snd` to get just the value `i`. My first draft did `maximum[(p i,i)|i<-[0..n-1]]`, but this tiebreaks equal `p i`'s to higher `i`'s whereas we want lower. Negating `p i` and finding the minimum fixes this.

We can negate `p i` directly in its definition without costing any bytes by subtracting `1` each step rather than adding `1`. It doesn't hurt to start from `0` rather than `-1` for the base case, since shifting `p` by a constant doesn't affect comparisons.

**82 bytes**

```
f n=snd$minimum[(p i,i)|i<-[0..n-1]]
p n|n>9=p(product$read.pure<$>show n)-1
p n=0

```

Try it online!

The code at the top implements `\i->(p i,i)` as `(,)=<<p` and maps it over the range, but unfortunately doesn't save any bytes with the parens it needs.
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~57~~ 56 bytes

```
MaximalBy[Range@#-1,#>9&&1+#0@@Times@@@RealDigits@#&,1]&

```

Try it online!

Returns the value wrapped in a list.

Since `MaximalBy` chooses the maximum based on Mathematica's internal ordering, choosing a value for the base case (when n≤9) isn't necessary.
> 2 votes

# Answer
# C (gcc), ~~95~~ 94 bytes

Saved a byte thanks to ceilingcat!!!

```
a;b;c;d;r;f(n){for(b=0;n--;r=c>=b?b=c,n:r)for(c=0,d=n;a=d,d=d>9;++c)for(;a;a/=10)d*=a%10;d=r;}

```

Try it online!
> 1 votes

---
Tags: code-golf, math, arithmetic, repeated-transformation
---


title: Row, Column, Diagonal, Block

text:
# Question
Title: Row, Column, Diagonal, Block
Write a square block of code that is N characters wide and N characters tall, for some positive integer N.

For instance, your N may be 5 and the block look like this:

```
ThisI
sMy5B
y5Cod
eBloc
kOkay

```

This block needs to behave as follows:

1. When the top row is extracted and run as a program, the exact text `row` needs to be printed to stdout.

For example, `ThisI` would print `row`.
2. When the left column is extracted and run as a program, the exact text `col` needs to be printed to stdout.

For example, `Tsyek` would print `col`.
3. When the main diagonal from the top left to the bottom right corners is extracted and run as a program, the exact text `dia` needs to be printed to stdout.

For example, `TMCoy` would print `dia`.
4. When the entire block is run as a program, **including the newlines** (with an optional trailing newline), the exact text `blk` needs to be printed to stdout.

For example,

```
ThisI
sMy5B
y5Cod
eBloc
kOkay

```

would print `blk`.

**Details**

* All four programs are run in the same programming language.
* The N2 characters in the original block may be anything but line terminators.
* If your language does not have an stdout, you may use another common output method. It must be the same method across all four programs.

**The submission whose original block contains the fewest distinct characters (not counting newlines) wins.** Tiebreaker goes to the submission with the smaller N.

# Answer
> 6 votes
# \>\<\> (Fish), 3 unique characters (N = 2000)

The code uses `1` and `-` to put arbitrary numbers on the stack and `p` to (self-)modify the code based on the top 3 numbers on the stack. E.g Putting a `!` at position `0 0` would look like `003b*p` in normal \>\<\> and with `p1-` it becomes `111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p`.

After the modification the instruction pointer (IP) wraps around the code and runs the modified part. In the "block" case the IP is redirected for further modification (then reredirected back) to differ from the "row" case. In the "row" case the same two redirection happens but there is no code in between them so they have no effect.

The final generated codes for the 4 cases (omitting the unchanged `p1-` parts):

```
row:      "wor"\ooo;

column:   "loc"ooo;

diagonal: "dia"ooo;

block:    "wor"\"klb"ooo;

```

The code size is 4 MB and the code is accessible here. (There is no difficulty running it.)

The generator python3 program is accessible here.

# Answer
> 14 votes
# CJam, ~~13~~ 12 unique characters, N = 5

```
"row"
cd;"a
oaiaa
l"aa;
"blk"

```

As straight forward as it gets

*UPDATE* : Converted space to `a` (no-op in this case) as pointed out by Runner112

Try it online here

# Answer
> 8 votes
# Bash, 19 unique characters, N = 19

```
trap echo\ row exit
t=t trap exit
t=t echo blk
exit
=
t    e
      c
e      h
c       o
h
o         d
           i
c           a
o
l

```
* The first row is `trap echo\ row exit`. This causes `echo row` to be executed when the script exits (just the first line)
* The first column is `ttt=t echo col`
* The diagonal is `t=tt echo dia`
* The full block works by canceling the EXIT handler set up in the first line, then `echo blk` then exits.

# Answer
> 6 votes
# \>\<\>, 14 unique characters, N = 10

```
"wor"\ooo;
     "
l a  k
o  i l
c   db
"    "
o    oo
o    o o
o    o  o
;    ;   ;

```

Pretty straightforward in a 2D language. The only tricky part is that we need the `\` to distinguish between `row` and `blk`.

# Answer
> 3 votes
# Brainfuck, 2 unique characters, N = 378

*With possible slight bending of rules.*

The program is a tad large, so here's a link to it on Pastebin.

The `row`, `col` and `dia` programs are straightforward. They simply increment the byte cell until the right ASCII code is reached and then outputs. If the letter has already passed, it increments until the cell overflows so it can start again at 0.

The `blk` program is where the slight rule bending occurs. In order to print the "exact text `blk`" as asked in the challenge, backspaces are used (ASCII code 8), which requires the displaying console/terminal to support it. Whenever errant values from the `row`/`col`/`dia` programs are printed, I ensure they are removed by outputting a few backspace control codes. To simplify things, I've ensured that all errant values outputted at one point are part of the printable ASCII range.

# Answer
> 2 votes
# C (gcc), 26 unique chars, N = 29

```
*w;main(){printf(w?w:"row");}
ww;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;/*;;;;;;;;;;;;;;;;;;;;;;;;
m;;m;;;;;;;;;;;;;;;;;;;;;;;;;
a;;;a;;;;;;;;;;;;;;;;;;;;;;;;
i;;;;i;;;;;;;;;;;;;;;;;;;;;;;
n;;;;;n;;;;;;;;;;;;;;;;;;;;;;
(;;;;;;(;;;;;;;;;;;;;;;;;;;;;
);;;;;;;);;;;;;;;;;;;;;;;;;;;
{;;;;;;;;{;;;;;;;;;;;;;;;;;;;
p;;;;;;;;;p;;;;;;;;;;;;;;;;;;
r;;;;;;;;;;r;;;;;;;;;;;;;;;;;
i;;;;;;;;;;;i;;;;;;;;;;;;;;;;
n;;;;;;;;;;;;n;;;;;;;;;;;;;;;
t;;;;;;;;;;;;;t;;;;;;;;;;;;;;
f;;;;;;;;;;;;;;f;;;;;;;;;;;;;
(;;;;;;;;;;;;;;;(;;;;;;;;;;;;
";;;;;;;;;;;;;;;;";;;;;;;;;;;
c;;;;;;;;;;;;;;;;;d;;;;;;;;;;
o;;;;;;;;;;;;;;;;;;i;;;;;;;;;
l;;;;;;;;;;;;;;;;;;;a;;;;;;;;
";;;;;;;;;;;;;;;;;;;;";;;;;;;
);;;;;;;;;;;;;;;;;;;;;);;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
};;;;;;;;;;;;;;;;;;;;;;;};;*/
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;*w="blk";

```

Try it online!

# Answer
> 2 votes
# V (vim), 11 unique characters, N=6

```
irow␛␛
cdddd␛
o␛i␛␛␛
l␛␛a␛␛
␛kdd␛␛
␛iblk␛

```

Try it online!

lot of escapes here. N=5 might be achievable, but I can't see a way to do it without increasing the unique characters.

# Answer
> 1 votes
# Ruby, 24 unique chars, N=17

```
trap(0){$><<:row}
rr=a=:blk;%;00000
a0a00000000000000
p00p0000000000000
(000(000000000000
00000000000000000
)00000)0000000000
{000000{000000000
$0000000$00000000
>00000000>0000000
<000000000<000000
<0000000000<00000
:00000000000:0000
c000000000000d000
o0000000000000i00
l;;trap(0){$><<a;
};000000000000;{}

```

Try it online!

---
Tags: code-golf, kolmogorov-complexity, source-layout
---


title: Simplify a continued fraction

text:
# Question
Title: Simplify a continued fraction
Continued fractions are expressions that describe fractions iteratively. They can be represented graphically:

$$ a\_0 +\cfrac 1 {a\_1 + \cfrac 1 {a\_2 + \cfrac 1 {\ddots + \cfrac 1 {a\_n} } } } $$

Or they can be represented as a list of values: \\$\[a\_0 ; a\_1, a\_2, \dots, a\_n\]\\$

### The challenge:

take a base number: \\$a\_0\\$ and a list of denominator values: \\$\[a\_1, a\_2, \dots, a\_n\]\\$ and simplify the continued fraction to a simplified rational fraction: return or print numerator and denominator separately.

### Examples:

* \\$\sqrt 19\\$: `[4;2,1,3,1,2]: 170/39`
* \\$e\\$: `[1;0,1,1,2,1,1]: 19/7`
* \\$\pi\\$: `[3;7,15,1,292,1]: 104348/33215`
* \\$ϕ\\$: `[1;1,1,1,1,1]: 13/8`

### Example implementation: (python)

```
def foo(base, sequence):
    numerator = 1
    denominator = sequence[-1]
    for d in sequence[-2::-1]:
        temp = denominator
        denominator = d * denominator + numerator
        numerator = temp
    return numerator + base * denominator, denominator
```

### Winning:

shortest code in bytes: --no builtins that do the entire problem allowed--

# Answer
> 15 votes
# J, ~~8~~ 5 bytes

Same as this, but uses a build-in for rationals.

Argument is {a0,a1,a2,a3,...} as a list of J extended precision rational numbers. Result is the fraction as a J extended precision rational number.

```
(+%)/

```

`(+%)` the plus-the-reciprocal-of

`/` reduction over

Try it online!

-3 thanks to miles.

# Answer
> 13 votes
## Haskell, ~~37~~ ~~36~~ 18 bytes

```
foldr1$(.(1/)).(+)

```

This function expects Haskell's `Ratio` type as input. Usage example:

```
Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2]
170 % 39

```

Note: one explicit `Ratio` in the input list (`4%1`) is enough, the type systems figures out that the others have to be `Ratio`s, too.

Edit: @Lynn saved a byte. Thanks!

Edit II: removed the `import` (see this discussion on meta).

# Answer
> 12 votes
## GolfScript, 13 bytes

```
~]-1%{\-1?+}*

```

Try it online!

Yay for GolfScript's hidden rationals. :)

### Explanation

GolfScript's only "official" number type is integers. But the exponentiation operator doesn't cast its result to integer and conveniently the native result of an integer exponentiation in Ruby (the language of GolfScript's interpreter) is a rational number. So we can easily get fractions by raising something to the power of -1. Conveniently, we want reciprocals anyway...

```
~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*

```

# Answer
> 12 votes
# LabVIEW, 36 equivalent bytes

Fairly straight forward naive implementation using OP's algorithm. Is there a nicer way to do this?

# Answer
> 11 votes
## Mathematica, ~~23~~ 22 bytes

```
Fold[#2+1/#&]@*Reverse

```

Essentially a port of my GolfScript answer. Here are some alternatives:

For 24 bytes, we can write a recursive variadic function:

```
f@n_=n
n_~f~m__:=n+1/f@m

```

For 21 bytes, we can even define a "variadic operator", but its calling convention would be so weird, that I'm reluctant to count this one:

```
±n_=n
n_ ±m__:=n+1/±m

```

You would have to call this with a *sequence* of the input values, e.g. `±Sequence[3, 7, 15, 1, 292, 1]` or `±##&[3, 7, 15, 1, 292, 1]`.

And also for 21 bytes, there would be the (forbidden) built-in:

```
FromContinuedFraction

```

# Answer
> 7 votes
# Dyalog APL, 10 bytes

Does not even use a build-in for rationals.

Takes {a0,a1,a2,a3,...} as argument, returns {denominator,numerator}.

```
1(,÷∨)+∘÷/

```

`1(,÷∨)` 1-prepended-to divided by the GCD of 1 and

`+∘÷` plus-the-reciprocal-of

`/` reduction over

TryAPL online!

# Answer
> 7 votes
## Python 2, 62 bytes

```
a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

```

It's unfortunately not as golfy (see @xnor's answer for shorter), but it calculates the fraction without needing to reverse the input. This uses the "magic table" approach for convergents – given the last two fractions `a/c` and `b/d`, the next fraction is `(n*b+a)/(n*c+d)`.

For instance, for pi:

```
          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

```

We can see that `15*22 + 3 = 333`, `15*7 + 1 = 106`, `1*333 + 22 = 355`, `1*106 + 7 = 113`, etc.

# Answer
> 5 votes
# M, 5 bytes

```
Ṛİ+¥/

```

The input is a list of the values `[a0, a1, ..., aN]` and it outputs a rational number.

Try it online! or Verify all test cases.

## Explanation

```
Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly

```

# Answer
> 5 votes
## Haskell, 30 bytes

```
foldr(\h(n,d)->(h*n+d,n))(1,0)

```

Recursively adds each layer going outward, updating `n/d` to `h+(1/(n/d))`, which equals `h+d/n` or `(h*n+d)/n`. The fraction is stored as a tuple of `(num,denom)`. The initial fraction of `(1,0)` flips to `0/1` which is `0`.

# Answer
> 4 votes
## Python, 50 bytes

```
f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

```

Builds the continued fraction from the end of the list going backwards, repeatedly updating the fraction `n/d` on the last element `x` as `n/d -> 1+1/(n/d) == (x*n+d)/n`.

# Answer
> 4 votes
## Common Lisp, 54

A somewhat verbose fold-right:

```
(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

```

### Tests

```
PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39
T     ℯ     19/7                 19/7
T     π     104348/33215         104348/33215
T     ϕ     13/8                 13/8

```

# Answer
> 3 votes
# Julia (53 Bytes)

This is my first time ever using Julia, if I overlooked an iterator I could have used to lose some more bytes, let me know. Here's a hint to anyone who doesn't know what language to choose for this specific challenge: https://en.wikipedia.org/wiki/Rational\_data\_type

```
f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)

```
* Reverse the input array.
* Iterate through it with rational division.
* Add c to the decimal result.

# Answer
> 3 votes
# 05AB1E, ~~19~~ 17 bytes

```
R¬V¦vyY*X+YUV}YX)

```

**Explanation**

Input taken as a list of numbers

```
                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

```

Try it online!

# Answer
> 3 votes
## Javascript (ES6), 55 bytes

```
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

```

### Test cases

```
var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));
```

# Answer
> 3 votes
## CJam, ~~18~~ 16 bytes

```
XUq~W%{2$*+\}/]p

```

Online interpreter.

```
XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output

```

# Answer
> 3 votes
## JavaScript (ES6), 44 bytes

```
a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])

```

# Answer
> 2 votes
## Javascript (ES6), 50 bytes

```
f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

```

It's thanks to Arnauld's answer, before seeing it I was stuck to 66 bytes:

```
f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

```

Example:
Call: `f([1, 0, 1, 1, 2, 1, 1])`
Output: `Array [ 19, 7 ]`

# Answer
> 2 votes
# Perl 6, 24 bytes

```
{[R[&(1/*+*)]](@_).nude}

```

## Explanation:

* `1 / * + *` is a lambda with two parameters (`*`) which takes the reciprocal of the first, and adds the second. ( returns a Rat )
* `R[&(…)]` uses that as if it was an infix operator and reverses it.
( including making it right associative )
* `[…](@_)` takes that and uses it to reduce the input.
* `… .nude` returns the ***nu***merator and ***de***nominator of the Rat.
* `{ … }` make it a bare block lambda with implicit parameter `@_`.

## Usage:

```
say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)

```

# Answer
> 2 votes
## Zephyr, 145 bytes

```
input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

```

Zephyr is the first programming language I ever created. It was designed to be intuitive and have clean syntax--rather at the expense of brevity. Why am I golfing with it, you ask? Because, unlike any language I've written since, it has a built-in `Fraction` type. You can even use the division operator `/` as a unary operator for "inverse" (a feature I borrowed for Pip).

Now, there are significant limitations. The biggest problem for this challenge is that arrays must be defined with fixed size, which means that the program starts by reading the size of the array from the user. (I hope this is ok; the alternative is hardcoding the size.) There's also the minor problem that operator precedence doesn't exist, meaning multi-operator expressions have to have parentheses.

Here's an example run:

```
C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8

```

# Answer
> 2 votes
# APL(NARS), 15+1 chars, 30+2 bytes

```
{1=≢⍵:↑⍵⋄+∘÷/⍵}

```

Translation in Apl(Nars) from Adam J solution... the input allowed for that function will be all list of integer numbers, where the first element will be of type rational. Test:

```
  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}
  f 4x 2 1 3 1 2
170r39
  f 1x 0 1 1 2 1 1
19r7
  f 3x 7 15 1 292 1
104348r33215
  f 1x 1 1 1 1 1
13r8
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828
158824716824887954093160207727r52744031585005490644982548907
  f ,0x
0
  f ,9x
9

```

so it would be 15 chars as length of function and 1 char for "x" for enter the type of input I want and exit the type I want...

# Answer
> 2 votes
# Ruby, 34 bytes

```
->a{a.reverse.inject{|b,i|i+1r/b}}

```

This performs a right fold (by reversing and then left folding), adding each element to 1 over the running total (the elements to the right). Ruby has the Rational type, which is really nice. And literal rationals are a number suffixed with `r`.

# Answer
> 2 votes
# Stax, 4 bytes

```
╣╩┼►

```

Run and debug it

As small as it is, it's not a built-in. The built-in rationals help quite a bit though. Unpacked to ascii, the program is `rksu+`.

1. Reverse the array.
2. Fold the array using `(a, b) => (a + 1/b)`.

# Answer
> 1 votes
# Husk, 4 bytes

```
Ḟ·+\

```

Try it online!

pretty simple with `TNum` being a rational type.

# Answer
> 0 votes
# Vyxal, ~~6~~ 5 bytes

```
‡Ė+ḭƒ

```

Try it Online!

I added `foldr` lol.

## Explained

```
‡Ė+ḭƒ
‡Ė+    # lambda x, y: 1 / x + y
   ḭ   # reduce input by ↑, going right-to-left
    ƒ  # fractionify the result

```

---
Tags: code-golf, math, rational-numbers
---