title: Circularly moving sum

text:
# Question
Title: Circularly moving sum
*Inspired by a question at Stack Overflow*.

Given a non-empty array of integers `x` and a positive integer `n`, compute the **sum** of each **sliding block** of length `n` along the array `x`, **circularly** filling the missing values at the left with values from the right as follows:

* the first block contains the first entry of `x`, preceded by `n-1` circularly shifted entries;
* the second block has the first and second entries of `x`, preceded by `n-2` circularly shifted entries; and so on.

The output array `y` has the same size as `x`. It is possible for `n` to exceed the length of `x`, and then the values of `x` are circularly **reused several times**.

# Examples

### Example 1 (values are reused only once)

```
x = [2, 4, -3, 0, -4]
n = 3

```

give as output

```
y = [-2, 2, 3, 1, -7]

```

where

* `-2` is the sum of the block `[0, -4, 2]` (the first two values come from the circular shifting)
* `2` is the sum of `[-4, 2, 4]` (the first value comes from the circular shifting)
* `3` is the sum of `[2, 4, -3]` (no circular shifting necessary anymore)
* `1` is the sum of `[4, -3, 0]`
* `-7` is the sum of `[-3, 0, -4]`.

### Example 2 (values are reused several times)

```
x = [1, 2]
n = 5

```

give

```
y = [7, 8]

```

where

* `7` is the sum of the block `[1, 2, 1, 2, 1]` (the first four values have been circularly reused)
* `8` is the sum of the block `[2, 1, 2, 1, 2]` (the first three values have been circularly reused)

# Additional rules

* The algorithm should work for arrays of arbitrary size and for arbitrary integer values. It is acceptable if the program is limited by data type or memory restrictions; but positive as well as negative integer values must be handled.
* Input/output can be taken/produced by any reasonable means.
* Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
* Shortest code in bytes wins.

# Test cases

```
x, n, -> y

[2, 4, -3, 0, -4], 3          ->  [-2, 2, 3, 1, -7]
[1, 2], 5                     ->  [7, 8]
[2], 7                        ->  [14]
[-5, 4, 0, 1, 0, -10, -4], 4  ->  [-19, -15, -5, 0, 5, -9, -13]
[-5, 4, 0, 1, 0, -10, -4], 1  ->  [-5, 4, 0, 1, 0, -10, -4]
[-2, -1, 0, 1, 2, 3], 5       ->  [4, 3, 2, 1, 0, 5]
[-10, 0, 10], 4               ->  [-10, 0, 10]

```

# Answer
# Jelly, 5 bytes

```
ṙC€}S

```

Try it online!

### How it works

```
ṙC€}S  Main link. Arguments: A (array), n (positive integer)

   }   Apply the link to the left to the right argument (n).
 C€      Complement each; map (z -> 1-z) over [1, ..., n], yielding [0, ..., 1-n].
ṙ      Rotate A 0, ..., 1-n units to the left (i.e., 0, ..., n-1 units to the
       right), yielding a 2D array.
    S  Take the sum of the rows.

```
> 3 votes

# Answer
# MATL, ~~11~~ ~~10~~ ~~9~~ 7 bytes

*3 Bytes saved thanks to @Luis!*

```
:gyn&Z+

```

The first input is the size of the window and the second input is the array

Try it at MATL Online

**Explanation**

```
       % Implicitly grab the first input (n)
       %     STACK: { 3 }
:      % Create the array [1...n]
       %     STACK: { [1, 2, 3] }
g      % Convert it to a logical array, yielding an array of 1's of length n
       %     STACK: { [1, 1, 1] }
y      % Implicitly grab the second input and duplicate it
       %     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], [2, 4, -3, 0, -4]}
n      % Determine the length of the array
       %     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], 5}
&Z+    % Perform circular convolution
       %     STACK: { [-2, 2, 3, 1, -7] }
       % Implicitly display the result

```
> 7 votes

# Answer
# Mathematica, 29 bytes

```
RotateLeft[#,1-n]~Sum~{n,#2}&

```

Or the same length:

```
ListConvolve[1~Table~#2,#,1]&

```
> 6 votes

# Answer
## CJam (16 bytes)

```
{_2$*ew1fb\,~)>}

```

Online test suite. This is an anonymous block (function) which takes the array and the length on the stack and leaves an array on the stack.

### Dissection

```
{       e# Declare a block
  _2$*  e#   Repeat the array n times: this guarantees having enough windows even
        e#   if x is only a single element
  ew    e#   Take each window of n elements
  1fb   e#   Sum each of the windows
  \,~)  e#   Compute -n
  >     e#   Take the last n elements of the array of sums
}

```
> 6 votes

# Answer
## Haskell, 57 bytes

```
a#n|l<-length a=[sum[a!!mod j l|j<-[i-n..i-1]]|i<-[1..l]]

```

Try it online!

Just some index looping and accessing the input list at indices modulo the length of the list.
> 4 votes

# Answer
# Haskell, ~~69~~ ~~65~~ 64 bytes

```
r=reverse
s#n=r$init[sum$take n$x++cycle(r s)|x<-scanr(:)[]$r s]

```

Try it online! Example usage: `[2, 4, -3, 0, -4] # 3`.

---

Using `n` *succeeding* instead of *preceding* entries could be ~~50~~ 46 bytes (getting rid of the reverse at the beginning and the end):

```
s#n=init[sum$take n$x++cycle s|x<-scanr(:)[]s]

```

Try it online!
> 3 votes

# Answer
# Pyth, ~~18~~ 16 bytes

*Saved 2 bytes thanks to @FryAmTheEggman!*

```
JEms<.>*JQ-JhdJl

```

**Try it here or Verify all the test cases.**

Fixed all the flaws at a cost of *-6 bytes*! Thanks a lot to Luis for making me understand the task in chat.

---

# Explanation (to be updated)

```
KEms<>_*QhK-lQhdKU - Full program.

KE                 - Assign the second input to a variable K.
  m              U - Map over the range [0...len(first input)).
       *QhK        - First input * (Second input + 1).
      _            - Reverse.
     >     -lQhd   - All the elements of the above after len(x)-current element-1
    <          K   - Up until the second input.
   s               - Sum.

```
> 2 votes

# Answer
# Japt, 12 bytes

```
ËVo rÈ+UgE-Z

```

Try it online!

TIO doesn't support the `Ë`, so the TIO link won't work. Instead, try it here.
> 2 votes

# Answer
# Kotlin, ~~141~~ ~~140~~ 138 bytes

Just a first go

## Submission

```
fun c(a:List<Int>,n:Int):List<Int>{
return (0..(a.size-1)).map{var t=0
for (o in 0..(n-1)){var i=it-o
while(i<0) {i+=a.size};t+=a[i]}
t}}

```

## Beautified

```
fun c(a: List<Int>, n: Int): List<Int> {
    return (0..(a.size - 1)).map {    // Iterate over the items
        var t = 0                     // Start the total at 0
        for (o in 0..(n - 1)) {       // Start at the item, go over the window backwards
            var i = it - o            // -------------------------
            while (i < 0) {           //  Make the index in range
                i += a.size           //
            }                         // -------------------------
            t += a[i]                 // Add the item to the total
        }
        t                             // Return the total
    }
}

```

## TryItOnline

# Edits

* Removed newline on before last closing bracket
> 2 votes

# Answer
# Java 8, 102 bytes

Lambda (curried) from `int[]` to lambda from `Integer` to `int[]`. Assign to `Function<int[], Function<Integer, int[]>>`.

```
a->n->{int l=a.length,o[]=new int[l],i=0,j;for(;i<l;i++)for(j=i-n;j++<i;)o[i]+=a[(j%l+l)%l];return o;}

```

Try It Online

## Ungolfed lambda

```
a ->
    n -> {
        int
            l = a.length,
            o[] = new int[l],
            i = 0,
            j
        ;
        for (; i < l; i++)
            for (j = i - n; j++ < i; )
                o[i] += a[(j % l + l) % l];
        return o;
    }

```

`(j % l + l) % l` computes a nonnegative remainder for any `j`. Taken from here.
> 2 votes

# Answer
# C, 91 bytes

```
i,j,k,s;f(a,l,n)int*a;{for(i=0;i<l;printf("%d ",s))for(j=n*l+i++,k=n,s=0;k--;)s+=a[j--%l];}

```

Try it online!
> 2 votes

# Answer
# Octave, 53 bytes

```
@(x,n)shift(imfilter(x,+!!(1:n),'circular'),fix(n/2))

```

Try it online!

* The `imfilter` function with option `circular` computes the circular convolution at the center of window so the result should be shifted.
> 2 votes

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

```
{@^a;[«+»] map {@a.rotate(-$_)},^$^b}

```

Try it online!

My first Perl 6 entry. Can probably be improved.
> 2 votes

# Answer
# 05AB1E, 10 bytes

```
.×ŒùOR¹g£R

```

Try it online!

**Explanation**

```
.×           # repeat input_1 input_2 times
  Œù         # push all sublists of size input_2
    O        # sum each
     R       # reverse the list
      ¹g£    # take the first len(input_1) items
         R   # reverse the list

```
> 2 votes

# Answer
# , ~~101~~ ~~93~~ 89 bytes

```
function(x,n,w=sum(x|1)){for(j in 1:w)F=c(F,sum(c(tail(rep(x,n),n-1),x)[1:n+j-1]))
F[-1]}

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~69~~ 61 bytes

**\- 8 bytes Thanks a lot @muru**

```
lambda x,n:[sum((x[-n+1:]+x*n)[i:i+n])for i in range(len(x))]

```

Try it online!

Explanation:

First we need to ensure there is enough numbers on the left of the original list, this is acheived by the `x*n+x` part.

For, example: `[2,4,-3,0,4],5`:

```
                   ,2,4,-3,0,-4
 ....-4,2,4,-3,0,-4,2,4,-3,0,-4

```

Then we shall reverse the list:

```
 <original->
 -4,0,-3,4,2, -4,0,-3, 4........
           <-2's block->

```

Next we obtain corresponding blocks for each element by `[len(x)+~i:][:n]`. The slice will be reverse i.e. 2 will gain a block: `[2,-4,0,-3,4]` which is reverse of the expected `[4,-3,0,-4,2]`, but we need the sum after all. So, this works. :)
> 1 votes

# Answer
# JavaScript ES6 ~~80~~ 78 bytes

```
x=>n=>x.map((_,i)=>eval('for(L=x.length,N=0,j=++i-n;j<i;j++)N+=x[(j%L+L)%L]'))

```

2 bytes saved thanks to Neil

### Usage:

```
f=x=>n=>x.map((_,i)=>eval('for(L=x.length,N=0,j=++i-n;j<i;j++)N+=x[(j%L+L)%L]'))

f([2, 4, -3, 0, -4])(3)

```
> 1 votes

# Answer
# Röda, 52 bytes

```
f a,n{(a*n)|slide n|tail#a*n|{head n|sum}while open}

```

Try it online!

Explanation:

```
f a,n{
  (a*n)|    /* Push the items in a n times to the stream */
  slide n|  /* Create a sliding block of length n */
  tail#a*n| /* Push the last n*len(a) values in the stream to the stream */
  {         /* While there are elements in the stream (stream is open): */
    head n| /*   Pull n values from the stream */
    sum     /*   Sum them and push the sum to the stream */
  } while open
}

```
> 1 votes

# Answer
# Perl 5, 66 + 1 (-a) = 67 bytes

```
$n=pop@F;$,=$";say map{$q=$c++;$t=0;$t+=$F[$q--%@F]for 1..$n;$t}@F

```

Try it online!
> 1 votes

# Answer
# K (oK), 18 bytes

**Solution:**

```
{+/+y':(1-y+#x)#x}

```

Try it online!

**Examples:**

```
{+/+y':(1-y+#x)#x}[1 2;5]
7 8
{+/+y':(1-y+#x)#x}[-5 4 0 1 0 -10 -4;4]
-19 -15 -5 0 5 -9 -13
{+/+y':(1-y+#x)#x}[-10 0 10;4]
-10 0 10

```

**Explanation:**

Was about to post a **31 byte** solution then I remembered that oK has a built-in for sliding windows...

```
{+/+y':(1-y+#x)#x} / the solution
{                } / lambda with implicit x and y parameters
               #x  / take (#) from list x
       (    #x)    / length of x
          y+       / add y (window size)
        1-         / subtract from 1 to give a negative
    y':            / sliding window of size y
   +               / flip
 +/                / sum

```

**Bonus:**

The **31 byte** solution that also works in K4:

```
q)k){+/+x#y#'|+(:':\|(1-y+x:#x)#x)}[2 4 -3 0 -4;3]
-2 2 3 1 -7

```
> 1 votes

# Answer
# Japt, 8 bytes

```
£gVonY)x

```

Try it

```
£gVonY)x     :Implicit input of array U=x & integer V=n
£            :Map each 0-based index Y in U
 g           :  Get the elements in U at 0-based indices
  Vo         :    Range [0,V)
    nY       :    Subtract each from Y
      )      :  End indexing
       x     :  Reduce by addition

```
> 1 votes

---
Tags: code-golf, math, arithmetic, array, integer
---


title: Find the nth Aaron number

text:
# Question
Title: Find the nth Aaron number
# Background

A Ruth-Aaron pair is a pair of consecutive positive integers `n` and `n+1` such that the sum of the prime factors (counting repeated prime factors) of each integer are equal. For example, `(714,715)` is a Ruth-Aaron pair, since `714=2*3*7*17`, `715=5*11*13`, and `2+3+7+17=5+11+13=29`. The name Ruth-Aaron pair was chosen by Carl Pomerance in reference to Babe Ruth's career home run total of `714`, which stood as the world record from May 25, 1935 until April 8, 1974 when Hank Aaron hit his `715`th home run. You can learn more about the fascinating history of these numbers in this Numberphile video.

# Goal

Write a complete program or function which, given a positive integer `n`, outputs the `n`th Aaron number, where the `n`th number is defined to be the larger integer of the `n`th Ruth-Aaron pair. Thus the `n`th Aaron number is `a(n)+1`, where `a(n)` is the `n`th term in the OEIS sequence A039752.

# Test cases

The first few Aaron numbers are

```
6,9,16,78,126,715,949,1331,1521,1863,2492,3249,4186,4192,5406,5561,5960,6868,8281,8464,10648,12352,14588,16933,17081,18491,20451,24896,26643,26650,28449,28810,33020,37829,37882,41262,42625,43216

```

# Rules

# Answer
# 05AB1E, ~~11~~ ~~10~~ 9 bytes

-1 byte thanks to Emigna
-1 byte thanks to Adnan

```
µN>Ð<‚ÒOË

```

Explanation:

```
µ            While the counter variable (which starts at 0) is not equal to the input:
 N>          Store the current iteration index + 1, and then create an array with
   Ð<‚       [current iteration index + 1, current iteration index]
      ÒO     Get the sum of the prime factors of each element
        Ë    If all elements in the array are equal,
             implicitly increment the counter variable

```

1-indexed.

Try it online!
> 7 votes

# Answer
# Husk, ~~11~~ 9 bytes

-2 bytes thanks to a clever golf by @Leo

```
€∫Ẋ¤=oΣpN

```

Try it online!

### Explanation

```
  Ẋ     N   -- map function over all consecutive pairs ... of natural numbers           [(1,2),(2,3),(3,4),(4,5)...]
   ¤=       --   are the results of the following function equal for both in the pair?
     oΣp    --     sum of prime factors                                                   [0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0]
 ∫          -- cumulative sum                                                           [0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3]
€           -- the index of the first value equal to the input

```
> 6 votes

# Answer
# Jelly, 12 bytes

```
;‘ÆfS€Eµ⁸#Ṫ‘

```

A monadic link taking and returning non-negative numbers

**Try it online!**

### How?

```
;‘ÆfS€Eµ⁸#Ṫ‘ - Link: number, n
         #   - n-find (counting up, say with i, from implicit 1)
        ⁸    - ...number of matches to find: chain's left argument, n
       µ     - ...action: the monadic chain with argument i:
 ‘           -   increment = i+1
;            -   concatenate = [i,i+1]
  Æf         -   prime factors (with duplicates, vectorises)
    S€       -   sum €ach
      E      -   all (two of them) equal?
          Ṫ  - tail, the last matching (hence nth) i
           ‘ - increment (need to return i+1)

```
> 3 votes

# Answer
# MATL, 17 bytes

```
`@:"@Yfs]vd~sG<}@

```

1-based. Very slow.

**Try it online!**

### Explanation

```
`        % Do...while
  @      %   Push iteration index k, starting at 1
  :      %   Range [1 2 ... k]
  "      %   For each j in [1 2 ... k]
    @    %     Push j
    Yf   %     Row vector of prime factors
    s    %     Sum
  ]      %   End
  v      %   Concatenate whole stack into a column vector
  d      %   Consecutive differences. A zero indicates a Ruth-Aaron pair
  ~s     %   Number of zeros
  G<     %   Is it less than the input? If so: next k. Else: exit loop
}        % Finally (execute right before when the loop is exited)
  @      %   Push current k
         % Implicit end. Implicit display

```
> 3 votes

# Answer
# Pyth, ~~23~~ 20 bytes

This is 1-indexed.

```
WhQ=-QqsPZsPhZ=+Z1;Z

```

**Test Suite** or **Try it online!**

---

# Explanation

```
WhQ=-QqsPZsPhZ=+Z1;Z  - Full program. Takes input from Standard input.

WhQ                      - While Q is still higher than 0.
       sPZ               - Sum of the prime factors of Z.
          sPhZ           - Sum of the prime factors of Z+1.
      q                  - If the above are equal:
   =-Q                     - Decrement Q by 1 if they are equal, and by 0 if they are not.
              =+Z1;      - Increment Z on each iteration.
                   Z     - Output Z.

```
> 3 votes

# Answer
# PHP, ~~93 92~~ 91+1 bytes

```
while(2+$argn-=$a==$b)for($b=$a,$a=!$x=$n+=$k=1;$k++<$x;)for(;$x%$k<1;$x/=$k)$a+=$k;echo$n;

```

Run as pipe with `-nR` or try it online.

-2 bytes with 3-indexed (fist Aaron number for argument `3`): remove `2+`.

**breakdown**

```
while(2+$argn       # loop until argument reaches -2 (0 and 1 are false positives)
    -=$a==$b)           # 0. if factors sum equals previous, decrement argument
    for($b=$a,          # 1. remember factors sum
        $a=!            # 3. reset factors sum $a
        $x=$n+=         # 2. pre-increment $n and copy to $x
        $k=1;$k++<$x;)  # 4. loop $k from 2 to $x
        for(;$x%$k<1;       # while $k divides $x
            $x/=$k)             # 2. and divide $x by $k
            $a+=$k;             # 1. add $k to factors sum
echo$n;             # print Aaron number $n

```
> 3 votes

# Answer
# Mathematica, 97 bytes

```
(t=r=1;While[t<=#,If[SameQ@@(Plus@@((#&@@# #[[2]])&/@FactorInteger@#)&/@{#,#+1}&@r),t++];r++];r)&

```

Try it online!
> 3 votes

# Answer
# Pyth, 12 11 bytes

```
e.fqsPtZsPZ

```

Indexing from 1 removes a byte, and puts Pyth ahead of Jelly

---

# Explanation

```
e.fqsPtZsPZ  - Full program. Takes input from Standard input.

e.f          - Last element of the list of the first $input numbers for which
   q         - Are equal
    s   s    - The sum of
     PtZ PZ  - Prime factors of $number-1 and $number

```
> 2 votes

# Answer
# Jelly, 17 bytes

```
ÆfS=’ÆfS$$µ³‘¤#ṖṪ

```

Try it online!

# Explanation

```
ÆfS=’ÆfS$$µ³‘¤#ṖṪ  Main link, argument is z
              #    Find the first       elements that satisfy condition y: <y><z>#
           ³‘¤                    z + 1
          µ        Monadic link, where the condition is:
  S                The sum of
Æf                            the array of primes that multiply to the number
   =               equals
       S           The sum of
     Æf                       the prime factors of
    ’                                              the number before it
        $$         Last two links as a monad, twice
               Ṗ   k -> k[:-1]
                Ṫ  Last element (combined with `pop`, gets the second last element)

```

1-indexed
> 1 votes

# Answer
# Ruby, ~~89~~ 86 bytes

```
->n{(1..1/s=0.0).find{|x|r,c=2,0
0while x%r<1?(x/=r;c+=r):x>=r+=1
(c==s)?0>n-=1:!s=c}}

```

Try it online!
> 1 votes

# Answer
# Japt, 19 bytes

```
1+_°k x ¥Zk x «U´}a

```

Uses 1-indexing.

Try it online!
> 0 votes

# Answer
# Python 2, ~~119 104 102~~ 101 bytes

```
f=lambda n,k=2:n/k and(f(n,k+1),k+f(n/k))[n%k<1]
i=input();g=0
while-~i:i-=f(g)==f(g+1);g+=1
print(g)

```

Try it online!

**-17 bytes** thanks to @ovs!

**-1 byte** thanks to @notjagan

Credit goes to Dennis for the prime factorization algorithm. 1-indexed.

---

> **Note:** This is extremely slow and inefficient. Inputs higher than 7 will crash unless you set `import sys` and do `sys.setrecursionlimit(100000)`, but it works in theory.
> 0 votes

# Answer
# Japt, 14 bytes

```
Èk x ¶Yk x}iU1

```

Try it
> 0 votes

# Answer
# Gaia, 13 bytes

```
⟨:)ḍΣ¤ḍΣ=⟩#e)

```

Try it online!
> 0 votes

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


# Question
Title: Return the nth digit of the sequence of aliquot series
### 0. DEFINITIONS

A *sequence* is a list of numbers.
A *series* is the sum of a list of numbers.
The set of *natural numbers* contains all "non-negative integers greater than zero".
A *divisor* (in this context) of a natural number *j* is a natural number *i*, such that *j*÷*i* is also a natural number.

### 1. PREAMBLE

A couple of other questions on this site mention the concept of the aliquot, or the sequence of divisors of a natural number *a* which are less than *a*. Determining amicable numbers involves computing the sum of these divisors, called an aliquot sum or aliquot series. Every natural number has its own aliquot sum, although the value of a number's aliquot sum is not necessarily unique to that number. (*Exempli gratia*, every prime number has an aliquot sum of 1.)

### 2. CHALLENGE

Given a natural number `n`, return the `n`th digit of the sequence of aliquot sums. The first several series in the sequence, starting with the series for 1, are:

```
{0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13}

```

Concatenated, these look like:

```
0113161748116110915121122111413661613

```

Input may be zero-indexed or one-indexed, according to your preference. Solutions must be programs or functions capable of returning the 10,000th digit (input up to `9999` or `10000`). The shortest working solution wins.

### 3. TEST CASES

Correct input-output pairs should include, but are not limited to, the following:

```
   0 or     1    ->    0
   4 or     5    ->    1
  12 or    13    ->    6
9999 or 10000    ->    7

```

The number preceding the "or" is 0-indexed; the number following is 1-indexed.
Additional test cases may be provided upon request.

### 4. REFERENCES

OEIS has a list of numbers and their aliquot sums.

# Answer
# 05AB1E, ~~14~~ ~~11~~ 10 bytes

Compute n = 9999 in about 15 seconds. Code:

```
ÌL€Ñ€¨OJ¹è

```

Explanation:

```
Ì           # Increment implicit input by 2
 L          # Generate the list [1 .. input + 2]
  €Ñ        # For each, get the divisors
    €¨      # For each, pop the last one out
      O     # Sum all the arrays in the array
       J    # Join them all together
        ¹è  # Get the nth element

```

Uses the **CP-1252** encoding. Try it online!.
> 6 votes

# Answer
## Mathematica, 51 bytes

```
Array[##&@@IntegerDigits[Tr@Divisors@#-#]&,#][[#]]&

```

An unnamed function which takes and returns an integer and uses 1-based indexing. Handles input `10000` instantly.

### Explanation

This is a very straight-forward implementation of the definition, making use of the fact that the first `n` divisor sums are always enough to determine the `n`th digit. As usual, the reading order of golfed Mathematica is a bit funny though:

```
Array[...&,#]...&

```

This generates a list with all the results of applying the unnamed function on the left to all the values `i` from `1` to `n` inclusive.

```
...Tr@Divisors@#-#...

```

We start by computing the divisors of `i`, summing them with `Tr` and subtracting `i` itself so that it's just the sum of divisors less than `i`.

```
...IntegerDigits[...]...

```

This turns the result into a list of its decimal digits.

```
##&@@...

```

And this removes the "list" head, so that all the digit lists are automatically concatenated in the result of `Array`. For more details on how `##` works, see the "Sequences of arguments" section in this post.

```
...[[#]]

```

Finally, we select the `n`th digit from the result.
> 6 votes

# Answer
# Pyth, ~~26~~ ~~21~~ ~~20~~ 15 bytes

```
@sm`sf!%dTtUdSh

```

Try it online. Test suite.

Uses 0-based indexing. The program is O(n²) and completes for *n* = 9999 in about 14 minutes on my 2008 machine.
> 4 votes

# Answer
# Brachylog, 40 bytes

```
:2-I,?:?:1yrc:Im.;0.
:1e:2f+.
>.>0,?:.%0

```

This is 1-indexed, takes about 0.15 seconds for `N = 100`, 15 seconds for `N = 1000`. I'm currently running for `N = 10000`, I'll report the run time once it ends (If my estimation is correct, it should take about 8 hours)

**Edit**: by fixing premature constraints propagation in Brachylog, it now (on a 3 bytes longer code) takes about `2.5` minutes for `10000` but returns an `out of global stack` error.

### Explanation

* Main Predicate: `Input = N`

```
:2-I,                 I = N - 2
     ?:?:1y           Find the N first valid outputs of predicate 1 with input N
           rc         Reverse and concatenate into a single number
             :Im.     Output is the Ith digit of that number
                 ;    Or (I strictly less than 0)
                  0.  Output is 0

```
* Predicate 1: computes the sum of the divisors

```
:1e                   Get a number between N and 1
   :2f                Find all valid outputs of predicate 2 with that number as input
      +.              Output is the sum of those outputs

```
* Predicate 2: unifies output with a divisor of the input

```
>.>0,                 Output is a number between Input and 0
     ?:.%0            Input is divisible by Output

```
> 4 votes

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

*2 bytes thanks to @Adnan and 1 more thanks to @Dennis.*

```
ÆDṖSDµ€Fị@

```

Try it online!

Uses 1-based indexing. Completes for *n* = 10000 in under 2 seconds online.
> 4 votes

# Answer
# PHP, 90 bytes

0 indexed

```
<?php for(;strlen($s)<=$a=$argv[1];$s.=$n)for($n=0,$j=++$i;--$j;)$i%$j||$n+=$j;echo$s[$a];

```

Absolutely not subtle or with a clever way of approaching it at all.
Also, as usual, produces three notices which are ignored.
> 3 votes

# Answer
# , 34 bytes

```
{[:;1<@":@(-~>:@#.~/.~&.q:)@+i.@>:

```

This is zero-indexed and uses the formula below to calculate the divisor sums.

## Explanation

```
{[:;1<@":@(-~>:@#.~/.~&.q:)@+i.@>:  Input: n
                                >:  Increment n
                             i.@    Create the range [0, 1, ..., n]
    1                       +       Add one to each to get [1, 2, ..., n+1]
          (               )@        For each value
                        q:            Get the prime factors
                   /.~&.              For each group of equal prime factors
                #.~                     Raise the first to the first power, the second
                                        squared and so on, and sum them
             >:@                        Increment that sum
                      &.q:            Reduce the groups using multiplication
           -~                         Subtract the initial value from that sum
       ":@                            Convert each to a string
     <@                               Box each
 [:;                                Unbox each and concatenate the strings
{                                   Select the character from that string at index n
                                    and return it

```
> 3 votes

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

```
:"@@q:\~fsV]vG)

```

Indexing is 1-based.

The last test case times out in the online compiler, but it does give the correct result with the offline compiler, in about 15 seconds.

**Try it online!**

```
:         % Take input n. Push [1 2 ... n]
"         % For each k in [1 2 ... n]
  @       %   Push k
  @q:     %   Push [1 2 ... k-1]
  \       %   Modulo. Zero values correspond to divisors
  ~f      %   Indices of zeros. These are the divisors
  s       %   Sum
  V       %   Convert to string
]         % End for each
v         % Concatenate all stack contents vertically
G)        % Take n-th digit. Implicitly display

```
> 3 votes

# Answer
## Haskell, 52 bytes

```
(([1..]>>= \n->show$sum[m|m<-[1..n-1],mod n m<1])!!)

```

Usage example: `(([1..]>>= \n->show$sum[m|m<-[1..n-1],mod n m<1])!!) 12`-\> `6`.

It's a direct implementation of the definition: foreach `n` sum it's divisors and convert it into a string. Concatenate all such strings and pick the element at the requested index. Haskell's laziness takes only as much `n`s from the infinite list `[1..]` as needed.
> 3 votes

# Answer
# Python 3.5, ~~103~~ ~~93~~ 92 bytes:

```
R=range;A=lambda f:''.join([str(sum([j for j in R(1,i)if i/j%1==0]))for i in R(1,f+1)])[f-1]

```

Pretty straightforward implementation of method described in post.

Try It Online! (Ideone)

Does not quite finish within the allotted 5 seconds in the online compiler for input `10000`, but it does finish on my machine for the same input within about 8.5 seconds.
> 2 votes

# Answer
# Husk, 8 bytes

```
!ṁödΣhḊN

```

Try it online!
> 2 votes

# Answer
## Octave, 71 bytes

This one is Octave only. It won't work in MATLAB. A virtual function is created which works on 1-indexed numbers. It can probably be simplified a bit further. Will have a look this evening.

```
@(x)c((c=num2str(arrayfun(@(n)sum(b(~rem(n,b=(1:n-1)))),1:x)))~=' ')(x)

```

You can try online here.

Simply run the command above, prefixed with `a=` or whatever (just so that you can use it multiple times), and then do `a(10000)` or whatever. It takes about 7 seconds to calculated that the 10000th digit is a 7.
> 1 votes

# Answer
## Java 8, 220 bytes

```
import java.util.stream.IntStream;
char a(int n){return IntStream.range(1,n+2).map(i->IntStream.range(1,i).filter(k->i%k==0).sum()).mapToObj(Integer::toString).collect(java.util.stream.Collectors.joining("")).charAt(n);}

```

Well, it's fast at least. It averages 0.3 seconds to get the 9999/10000th element on my machine. It generates only as many aliquot sums as the index you specified. This means the string will be slightly longer than your index in most cases, since some aliquot sums have 2 or more digits, but for the most part, it only generates as long of a string as we need.

Usage:

```
public static void main(String[] args) {
    System.out.println(a(0));
    System.out.println(a(4));
    System.out.println(a(12));
    System.out.println(a(9999));
}

```

Ungolfed:

```
public static void main(String[] args) {
    System.out.println(all(0));
    System.out.println(all(4));
    System.out.println(all(12));
    System.out.println(all(9999));
}

static int aliquotSum(int n) {
    return IntStream.range(1, n).filter(k -> n % k == 0).sum();
}

static IntStream sums(int n) {
    return IntStream.range(1, n + 2).map(i -> aliquotSum(i));
}

static String arraycat(IntStream a) {
    return a.mapToObj(Integer::toString).collect(java.util.stream.Collectors.joining(""));
}

static char all(int index) {
    return arraycat(sums(index)).charAt(index);
}

```
> 1 votes

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


title: Generate Linus Sequence

text:
# Question
Title: Generate Linus Sequence
# Definition

From the description on OEIS A006345:

> To find `a(n)`, consider either a `1` or a `2`. For each, find the longest repeated suffix, that is, for each of `a(n)=1,2`, find the longest sequence `s` with the property that the sequence `a(1),...,a(n)` ends with `ss`. Use the digit that results in the shorter such suffix. `a(1) = 1`.

# Worked-out Example

`a(1)=1`.

If `a(2)=1`, we will have the sequence `1 1` where the longest doubled substring from the end is `1`. If `a(2)=2` instead, then it would be the empty substring. Therefore `a(2)=2`.

When `n=6`, we choose between `1 2 1 1 2 1` and `1 2 1 1 2 2`. In the first choice, `1 2 1` is doubled consecutively from the end. In the second choice, it is `2` instead. Therefore, `a(6)=2`.

When `n=9`, we choose between `1 2 1 1 2 2 1 2 1` and `1 2 1 1 2 2 1 2 2`. In the first choice, the longest doubled consecutive substring is `2 1`, while in the second choice `1 2 2` is doubled consecutively at the end. Therefore `a(9)=1`.

# Task

Given `n`, return `a(n)`.

# Specs

* `n` will be positive.
* You can use 0-indexed instead of 1-indexed. In that case, please state so in your answer. Also, in that case, `n` can be `0` also.

# Testcases

The testcases are 1-indexed. However, you can use 0-indexed.

```
n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1

```

# References

# Answer
## Haskell, ~~146~~ ~~140~~ ~~137~~ ~~133~~ 118 bytes

```
s!l|take l s==take l(drop l s)=l|1<2=s!(l-1)
g[w,x]|w<x=1|1<2=2
a 1=1
a n=g$(\s x->(x:s)!n)(a<$>[n-1,n-2..1])<$>[1,2]

```
> 7 votes

# Answer
## Python, 137 bytes

```
def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))):
 for _ in[0]*n:s+=[r(s+[0])>r(s+[1])]
 return-~s[n]

```

This solution is using 0-based indexing.
> 6 votes

# Answer
# Jelly, ~~25~~ ~~24~~ ~~22~~ 20 bytes

**2 bytes thanks to Dennis.**

```
2;€µḣJf;`€$ṪLµÞḢ
Ç¡Ḣ

```

Try it online!

A port of my answer in Pyth.

```
Ç¡Ḣ   Main chain

 ¡    Repeat for (input) times:
Ç         the helper chain
  Ḣ   Then take the first element

2;€µḣJf;`€$ṪLµÞḢ  Helper chain, argument: z

2;€               append z to 1 and 2, creating two possibilities
   µ         µÞ   sort the possibilities by the following:
    ḣJ                generate all prefixes from shortest to longest
       ;`€            append the prefixes to themselves
      f   $           intersect with the original set of prefixes
           Ṫ          take the last prefix in the intersection
            L         find its length
                 Ḣ   take the first (minimum)

```
> 6 votes

# Answer
# Mathematica, 84 bytes

```
a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]

```
> 4 votes

# Answer
# Jelly, ~~30~~ ~~29~~ ~~28~~ ~~27~~ 24 bytes

```
;€¬;\€Z;/f;`€$ṪḢ;
1Ç¡o2Ḣ

```

Try it online! or verify all test cases.
> 3 votes

# Answer
# MATL, 34 bytes

```
vXKi:"2:"K@h'(.+)\1$'XXgn]>QhXK]0)

```

Try it online! or verify all test cases.

### Explanation

```
v             % Concatenate stack vertically: produces empty array
XK            % Copy to clipboard K. This clipboard holds the current sequence
i:            % Take input n. Generate vector [1 2 ... n]
"             % For each k in [1 2 ... n]
  2:          %   Push [1 2]. These are the possible digits for extending the sequence
  "           %     For each j in [1 2]
    K         %       Push contents of clipboard K (current sequence)
    @         %       Push j (1 or 2)
    h         %       Concatenate horizontally: gives a possible extension of sequence
    '(.+)\1$' %       String to be used as regex pattern: maximal-length repeated suffix
    XX        %       Regex match
    gn        %       Convert to vector and push its length: gives length of match
  ]           %    End. We now have the suffix lengths of the two possible extensions
  >           %    Push 1 if extension with "1" has longer suffix than with "2"; else 0
  Q           %    Add 1: gives 2 if extension with "1" produced a longer suffix, or 1
              %    otherwise. This is the digit to be appended to the sequence
  h           %    Concatenate horizontally
  XK          %    Update clipboard with extended sequence, for the next iteration
]             % End
0)            % Get last entry (1-based modular indexing). Implicitly display

```
> 2 votes

# Answer
# Python 2, 94 bytes

```
import re
s='1'
exec"s+=`3-int(re.search(r'(.*)(.)\\1$',s).groups()[1])`;"*input()
print s[-1]

```

Uses 0-based indexing. Test it on Ideone.
> 2 votes

# Answer
# Pyth, ~~46~~ 29 bytes

Took some inspiration from @Leaky Nun's excellent Pyth answer. Tried to see if there was a shorter way using strings. Still 3 bytes short!

```
huh.melM+kf!x>blTT._bm+dGS2Qk

```

You can try it out here.
> 2 votes

# Answer
# Pyth, 26 bytes

```
huh.mleq#.<T/lT2._b+RGS2QY

```

Test suite.

### Explanation

When `n = 6`, we choose between `1 2 1 1 2 1` and `1 2 1 1 2 2`.

We generate these two possibilities, and then look at their suffixes.

For the first one, the suffixes are: `1`, `2 1`, `1 2 1`, `1 1 2 1`, `2 1 1 2 1`, `1 2 1 1 2 1`.

We filter for doubled suffixes by checking if they are the same after rotating them for their length divided by 2 (it turns out that this check is not perfect, because it confirms `1` and `2` also).

We take the last doubled suffix and then take its length.

We then choose the possibility that corresponds to a minimum length generated above.

Then we proceed to the next value of `n`.

For the purpose of this program, it was golfier to generate the reversed array instead.

```
huh.mleq#.<T/lT2._b+RGS2QY
 u                      QY   repeat Q (input) times,
                             start with Y (empty array),
                             storing the temporary result in G:
                   +RGS2         prepend 1 and 2 to G,
                                 creating two possibilities
   .m             b              find the one that
                                 makes the following minimal:
                ._                   generate all prefixes
       q#                            filter for prefixes as T
                                     that equals:
         .<T/lT2                         T left-rotated
                                         by its length halved
      e                              take the last one
     l                               generate its length
  h                              take the first minimal one
h                                take the first one from the generated
                                 array and implicitly print it out

```
> 2 votes

# Answer
# Perl, 40 bytes

```
$a.=/(.*)(.)\1$/^$2for($a)x$_;$_=$a%5+1

```

The code is **39 bytes** long and requires the `-p` switch (**+1** byte).

The loop is inspired by the Perl solution on the relevant OEIS page, although I did come up independently with the regular expression.

Test it on Ideone.
> 2 votes

# Answer
# Retina, ~~51~~ 42 bytes

**9 bytes thanks to Martin Ender.**

```
.+
$*x
+`((.*)(^|2|(?<3>1))\2)x
$1$#3
!`.$

```

Try it online!

A port of this answer.
> 2 votes

# Answer
# JavaScript (ES6), 84

Index base 0

```
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

```

**Less golfed**

```
n=>{
  r = d => (s+d).match(/(.*)\1$/)[0].length;
  c = '1';
  for(s = c; n--; s += c)
    c = r(1) > r(2) ? 2 : 1;
  return c;
}

```

**Test**

```
F=
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

for(n=0;n<20;n++)console.log(n,F(n))
```
> 1 votes

# Answer
# Husk, 20 bytes

```
!¡λ◄(L←SnmDṫ:⁰)ḣ2);1

```

Try it online! or Verify first 20 values

Same algorithm as Leaky Nun's answers.
> 0 votes

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


title: Is this number secretly Fibonacci?

text:
# Question
Title: Is this number secretly Fibonacci?
# Background

Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more distinct Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer `n` is itself a Fibonacci number, we will call `n` "secretly" Fibonacci.

For example:

```
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci

140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci

```

## Notes

* The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number \<= n and subtract it from n until you reach 0
* All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.

# Challenge

Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.

## Input

You may take input in any reasonable format. You may assume the input will be a single positive integer.

## Output

Output one of two distinct results for whether the input is secretly Fibonacci. Examples include `True`/`False`, `1`/`0`, etc.

## Scoring

This is , so shortest answer in bytes wins! Standard loopholes are forbidden.

# Test Cases

```
Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

```

# Answer
> 10 votes
# JavaScript (Node.js), 54 bytes

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

```

Try it online!

# Answer
> 9 votes
# Python 2, 77 bytes

```
def f(n):z=[bin(x).count('1')for x in range(n*n+1)if x&2*x<1];print z[z[n]]<2

```

Try it online!

This makes use of the theorem that the two descriptions of OEIS A003714 are equivalent:

> Fibbinary numbers: if \\$n = F(i\_1) + F(i\_2) + \dots + F(i\_k) \\$ is the Zeckendorf representation of \\$n\\$ (i.e., write \\$n\\$ in Fibonacci number system) then \\$a(n) = 2^{i\_1} + 2^{i\_2} + \dots + 2^{i\_k}\\$. **Also** numbers whose binary representation contains no two adjacent \\$1\\$'s.

We generate enough\* such numbers, and then use `z` as a mapping from non-negative integers to “how many terms are in the Zeckendorf representation of \\$n\\$?” by counting 1s in binary.

Then it remains to check if `z[n]` is a Fibonacci number, i.e. `z[z[n]] == 1`.

<sup>\*At least, \\$n^2+1\\$ *feels* like enough, and experimentally it seems to be enough. I'll prove this some time later.</sup>

# Answer
> 6 votes
# Jelly, 15 bytes

```
‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị

```

A monadic link accepting a non-negative integer which yields `1` if "Secretly Fibonacci" and `0` otherwise.

**Try it online!** (too inefficient for the larger test cases)

### How?

```
‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị - Link: integer, I
        µƬ      - perform the monadic link to the left as a function of the current I,
                - collecting up all the inputs until the results are no longer unique:
‘               -   increment I -> I+1
 ÆḞ€            -   nth Fibonacci number for €ach n in [1,I+1]
     R          -   range from 1 to I
    f           -   filter discard (discard Fibonacci numbers not in the range, i.e. > I)
      Ṫ         -   tail (get the largest)
       ạ        -   absolute difference with I
                - This gives us a list from I decreasing by Fibonacci numbers to 0
                - e.g. for 88 we get [88,33,12,4,1,0]
                -      because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88
          L     - length (the number of Fibonacci numbers required plus one)
           ’    - decrement (the number of Fibonacci numbers required)
            Ɗ   - treat the last three links (which is everything to the left) as a monad:
             ⁺  - ...and repeat it
                - i.e. get the number of Fibonacci numbers required for the number of
                -      Fibonacci numbers required to represent I.
                -      This is 1 if I is Secretly Fibonacci, and greater if not)
              Ị - insignificant? (is the absolute value of that <= 1?)

```

# Answer
> 5 votes
# , 83 bytes

```
function(n){T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n){n=n-T[T<=n][1]
F=F+1}
F%in%T}

```

Try it online!

# Answer
> 5 votes
# C# (.NET Core), 124 115 98 bytes

```
a=>{int n=0,b,c;for(;a>0;a-=b,n++)for(b=c=1;c<=a;b=c-b)c+=b;for(b=c=1;c<n;c+=b)b=c-b;return c==n;}

```

Try it online!

*-3 bytes: changed while loop to for (thanks to Olivier Grégoire)*
*-6 bytes: switched returns to use variable, initialized b and c outside of loops (thanks to Kevin Cruijssen)*
*-17 bytes: changed condition in second loop to move if out of loop and combine with return, reused b and c variables in last loop (thanks to raznagul)*

Ungolfed:

```
a => {
    int n = 0, b, c;                        // initialize variables

    for(; a > 0; a -= b, n++)               // increase n until a is 0
        for(b = c = 1; c <= a; b = c - b)   // set b and c to 1 for each a; set second largest Fibonacci number until largest Fibonacci number reaches a
            c += b;                         // set largest Fibonacci number of current sequence

    for(b = c = 1; c < n; c += b)           // while e is less than or equal to n, continue incrementing largest (e) Fibonacci number in the sequence
        b = c - b;                          // increment second-largest (d) Fibonacci number

    return c == n;                          // if c equals n, a is a secret Fibonacci number
}

```

# Answer
> 4 votes
# Perl 6, 58 bytes

```
{(1,&[+]...*>$_)∋($_,{$^n-(1,&[+]...^*>$n).tail}...0)-1}

```

Try it online!

`1, &[+] ... * > $_` is just the Fibonacci sequence, stopped at a convenient non-infinite place (the input number).

`$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0` is a sequence of numbers, starting with the input number, and each successive element obtained by subtracting the largest Fibonacci number less than or equal to the previous element from the previous element. The sequence terminates when `0` is reached. For example, if `$_` is `140`, then this sequence is `140, 51, 17, 4, 1, 0`.

Subtracting one from this sequence treats it as a number, its length, and the difference is the number of Fibonacci numbers which, added together, give the input number. Then this number is checked for membership in the first Fibonacci sequence.

# Answer
> 3 votes
# Perl 6, 48 bytes

```
{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}

```

Try it online!

Transforms the input to a list of Zeckendorf Representation repeatedly until it reaches a single number and then checks if the length of the sequence was less than 4.

The Zenckendorf function in the middle is mostly from Sean's answer with a couple of improvements.

### Explanation:

```
{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}
{                                              } # Anonymous code block
                                          ...     # Define a sequence:
    $_  # That starts at the input
      ,{                                 }  # Each element is defined by:
                                   ... # Another sequence that:
        $_,   # Starts at the previous element
            $_-   # The previous element minus
                1,&[+]...*     # The Fibonacci sequence
                          >$_  # Ending when it is larger than the previous element
               (             )[*-2]  # The second from last element
          {                        }...^0  # Run until 0, discarding the last element
         # This returns the length of the Zeckendorf Representation
                                         ...1  # Run this until it is length 1
 4>(                                         )  # Return true if the length of the sequence is smaller than 4

```

For example, the sequence for `2` is `2 1` since `2` is already a Fibonacci number. The sequence for `140` is `140 5 1`, and since 5 is a Fibonacci number this returns true. The sequence for `33` is `33 4 2 1`, and since `4` is not a Fibonacci number the sequence is of length 4.

# Answer
> 3 votes
# 05AB1E, 14 bytes

```
ΔDÅFθ-¼}¾ÅF¾<å

```

Try it online. No test suite for all test cases, because the `counter_variable` cannot be reset to 0.. I verified all by hand though, and they are correct.

**Explanation:**

```
Δ      }          # Loop until the top of the stack no longer changes
 D                #  Duplicate the top of the stack
                  #  (implicitly the input in the first iteration)
  ÅF              #  Get a list of all Fibonacci numbers lower than this number
    θ             #  Get the last item (largest one)
     -            #  Subtract it from the number
      ¼           #  Increase the counter_variable by 1 every iteration
        ¾         # After the loop, push the counter_variable
         ÅF       # Get all Fibonacci numbers below this counter_variable
           ¾<     # Push the counter_variable again, and subtract 1
             å    # Check if this value is in the list of Fibonacci numbers
                  # (and output implicitly)

```

NOTE: The `counter_variable` would be `5` for input `139` and `6` for input `140`, because in order for the `Δ`-loop to check the stack remained the same, it does of course an additional iteration.

# Answer
> 3 votes
# Haskell, 64 bytes

```
s=(<2).r.r
f=1:scanl(+)1f
r 0=0
r z=1+r(z-last(takeWhile(<=z)f))

```

Try it online!

# Answer
> 2 votes
# Retina 0.8.2, 61 bytes

```
.+
$*
M`((?>\2?)(\1|\G.))*..|.
.+
$*
^(((?>\3?)(\2|^.))*.)?.$

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
M`((?>\2?)(\1|\G.))*..|.

```

Count the number of Fibonacci numbers needed.

The first alternation deals with Fibonacci numbers that are at least 2. On the first pass, `\2` does not exist yet, but fortunately it's optional, so we don't have to match it. `\1` doesn't exist either, but fortunately we have the alternative of `\G.` which matches a single character at the start of the match. Both `\2` and `\1` therefore take on the value 1.

On subsequent passes, `\2` exists, so we try to match it. This time if it fails then `\1` also fails (since it is bigger than `\2`), but if it succeeds, the `(?>)` prevents backtracking, so if `\2` matches but `\1` does not we don't try just `\1`. (`\G1` always fails since we've advanced past the start of the patch.) Finally `\2` takes on the previous value of `\1` while `\1` takes on the sum of the two values.

We therefore match as many Fibonacci numbers as we can, adding as we go. Since the partial sums of the sequence `1, 2, 3, 5...` are `0, 1, 3, 6, 11...` i.e. 2 less than the Fibonacci numbers we finish by matching 2 at the end.

This obviously fails to match 1 itself so an alternation handles that case.

```
.+
$*

```

Convert to unary.

```
^(((?>\3?)(\2|^.))*.)?.$

```

Test whether this is a Fibonacci number. This uses the same idea as the first test but it uses `^` instead of `\G` and we also need to match exactly, so it uses an optional capture instead of an alternation as that's golfier (but it increases the capture numbers by 1).

# Retina, 35 bytes

```
.+
*
2}C`((?>\2?)(\1|\G.))*..|.
^1$

```

Try it online! Link includes test cases. Explanation:

```
.+
*

```

Convert to unary.

```
C`((?>\2?)(\1|\G.))*..|.

```

Count the number of Fibonacci numbers needed. (Looping both the conversion and count saves a whole byte over getting the count in unary in the first place.)

```
2}

```

Perform the previous steps twice in total. This takes the count of Fibonacci numbers needed to sum to the count of Fibonacci numbers.

```
^1$

```

If the number was secretly Fibonacci then the result is 1.

# Answer
> 1 votes
# Python 2, ~~146~~ 137 bytes

```
lambda a:len(g(len(g(a))))<2
f=lambda n:n<3or f(n-2)+f(n-1)
def g(a,n=1):j=f(n-1);return[j]if a-j<1else[j]+g(a-j)if a-f(n)<0else g(a,n+1)

```

Try it online!

f() is a recursive function that returns the value of the nth Fibonacci number. Taken from this answer.

g() is a recursive function that returns the Zeckendorf Representation of the given number as a list of integers.

Since all Fibonacci numbers will have a return length of one item from g(), h() checks if the length of the g() of g(n) == 1.

**EDIT:** Saved 9 bytes thanks to nedla2004. I keep forgetting that lambdas aren't always the best solution...

# Answer
> 0 votes
# Husk, 16 bytes

```
£İf←LU¡λ≠⁰→↑≤⁰İf

```

Try it online!

---
Tags: code-golf, decision-problem, fibonacci
---


title: Compute the Lambert W function

text:
# Question
Title: Compute the Lambert W function
Your challenge is to compute the Lambert W function. \\$W(x)\\$ is defined to be the real value(s) \\$y\\$ such that

$$y = W(x) \text{ if } x = ye^y$$

where \\$e = 2.718281828...\\$ is Euler's number.

Sometimes, \\$y\\$ may not be real.

### Examples

```
W(-1) = non-real
W(-0.1) = -0.11183, -3.57715
W(1) = 0.56714
W(2) = 0.85261

```

Here's a quick graph of what this function looks like.

---

### Rules

Your goal is to take an input and output either nothing, 1 solution, or 2 solutions, out to 5 significant figs. You should expect float inputs within the reasonable range of `-100..100`.

This is code-golf, so shortest code wins.

# Answer
# Octave, ~~36~~ 34 bytes

```
@(x)(y=lambertw(-1:0,x))(~imag(y))

```

Try it online!

I solved this in 10 different ways without the builtin, but I couldn't get the solution for both the `-1` branch and the `0`-branch. I wasn't able to solve this without resorting to the builtin `lambertw` function. Even though it uses a builtin, it's far from straightforward.

`lambertw` will only give out one value by default, namely the **W0(x)**, unless otherwise specified. The problem arises when we specifies that we want two values, both **W0(x)** and **W-1(x)**. If this is the case, and **x\>=0**, it will return one real and one complex result.

We therefore have to specify that we only want the results where the imaginary part of the result is zero.

### Breakdown:

```
@(x)                              % Anonymous function that takes x as input
    (y=lambertw(-1:0,x))          % The lambertw function, with both the -1 and 0 branches
                        (~imag(y))  % Index, where the elements with imag(y)=0 is true

```
> 3 votes

# Answer
# 05AB1E, ~~98~~ ~~86~~ ~~75~~ ~~74~~ 73 bytes

-11 bytes thanks to @KevinCruijssen

```
žr(zV"Ðžrsm*I-d"UY‹iõë∞.ΔX.V}®s‚ΔDÅAX.Vǝ}н,0‹i∞.Δ(X.V}(®‚ΔDÅAX.V≠ǝ}IYÊiн,

```

Try it online!

Explanation:

(I will let f(x)=x\*e^x)

```
žr(zV"Ðžrsm*I-d"U #Let Y=-1/e,X=str(ÐYsm*I-d) to save characters in the future

Y‹iõ              #if input<-1/e: print empty string

ë∞.ΔX.V}          #else: find least int k>=1 such that f(k)>=0 (evaluates string X as though it were a function)

®s‚               #make list [-1,k]

ΔDÅAX.Vǝ}         #find root of f(x)-input in the interval [-1,k] using bisection method

                  #actually this outputs a list with 2 numbers which will be very close to each other, which represents the interval in which the root lies

                  #e.g. the list [-3.00001,-3] would represent the interval [-3.00001,-3]

н,                #print the first item of the list; stack is currently empty

0‹i               #if input<0:

∞.Δ(X.V}(         #find greatest int k<=-1 such that f(k)>=0

®‚                #make list [k,-1]

ΔDÅAX.V≠ǝ}        #find root of f(x)-input in the interval [k,-1] using bisection method

                  #again, this outputs a list rather than a single number

IYÊiн,            #if input!=-1/e, print that root (done so that "-1" is not printed twice)

```

Visualization of the program's indentation:

```
žr(zV"Ðžrsm*I-d"UY‹iõë∞.ΔX.V}®s‚ΔDÅAX.Vǝ}н,0‹i∞.Δ(X.V}(®‚ΔDÅAX.V≠ǝ}IYÊiн,
                   {    {   }   {       }    {  {    }   {        }   {

```
> 2 votes

# Answer
# Ruby, 131 bytes

```
->x{y,z,e,l=1,-1,Math::E,->t{Math::log t};100.times{z=x<0&&x>-1/e ?l[x/z]:p;y=x<-1/e ?"non-real":x>e ?l[x/y]:x*e**-y};p y;z&&(p z)}

```

Try it online!

Basically applies fixed-point iteration 100 times, as partially explained in Lambert W function aproximation.
> 1 votes

# Answer
# C, 101 + 2 (`-lm`) bytes

Returns how many real solutions, and store them in an array.

This one is very slow, since it uses a brute-force approach to find roots. It handles up to x = 9e9.

```
f(a,b,p,t,c,x)float*b,a,x;{for(p=a<0,c=0,x=-50;x<9;x+=2e-6,p=t)(t=x*exp(x)>a)^p?b[c++]=x:0;return c;}

```

Try it online!

# C, ~~148~~ 146 + 2 (`-lm`) bytes

This function returns how many real solutions, and store them in the given pointers.

Use binary search to find a solution. It handles up to about x = 108.

```
#define h(x)99;for(l=-1;x=(l+r)/2,fabs(l-r)>1e-6;)x*exp(x)>a?r=x:(l=x);
f(a,b,c,l,r)float*b,*c,a,l,r;{r=h(*b)r=-h(*c)return-1/exp(1)>a?0:a<0?2:1;}

```

Try it online!
> 1 votes

# Answer
# Casio BASIC, 192 Bytes

A port of My 05AB1E answer

```
?→X
""
If X≥-e^-1
    Then 0→R
    While Re^R<X
        Isz R
    WhileEnd
    -1→L
    While Re^R>X
        .5(L+R→M
        If Me^M<X
            Then M→L
            Else M→R
        IfEnd
    WhileEnd
    If X<0
        Then M◢
        While Le^L<X
            Dsz L
        WhileEnd
        While Le^L≠X
            .5(L+R→M
            If Me^M<X
                Then M→R
                Else M→L
            IfEnd
        WhileEnd
        If M≠-1
            Then M

```

Note that indents are actually not supported; I added them for legibility.
> 1 votes

# Answer
# Forth (gforth), 144 bytes

```
: N 99 for fover fover fnegate fexp f* fover 2e f** f+ fswap 1e f+ f/ next f. ;
: f fdup 0e -1e fexp f- f> if 0e N fdup f0< if -2e N then then ;

```

Try it online!

Being stuck with the floating-point stack hurts a lot (with all the `f`-prefixes), but I guess it's pretty good score for a non-built-in after all.

Uses 100 iterations of Newton's method described here: given a previous estimate of \\$w=W(x)\\$, the next estimate \\$w'\\$ is calculated using the formula

$$ w' = \frac{xe^{-w}+w^2}{w+1} $$

I simplified the starting points for the golf: starting at 0 for primary branch (if \\$x \ge -1/e\\$) and -2 (inflection point) for secondary branch (if \\$-1/e \le x \< 0\\$) should suffice theoretically.

```
: N ( x w -- x )
  99 for                        \ ( x w ) run Newton's method 100 times...
    fover fover fnegate fexp f* \ ( x w x*e^-w )
    fover 2e f** f+             \ ( x w x*e^-w+ww )
    fswap 1e f+ f/              \ ( x (x*e^-w+ww)/(w+1) )
  next
  f.     \ Print the resulting w
;
: f ( x -- )
  fdup 0e -1e fexp f-  \ ( x x -1/e )
  f> if                \ ( x ) if less than -1/e, no solution
    0e N               \ ( x ) print primary solution
    fdup f0< if        \ ( x ) if less than 0, two solutions
      -2e N f.         \ ( x ) print secondary solution
    then
  then
;

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 28 bytes

```
x/.NSolve[#==E^x x,x,Reals]&

```

Try it online!

Returns `x` for no-solution.

This function should give all solutions because `NSolve` algorithm uses inverse functions, and there is a built-in inverse function of `x = y*(e^y)` called `ProductLog`.

### Explanation

```
#==E^x x

```

Equation `<input> = e^x * x`

```
NSolve[ ... ,x,Reals]

```

Find solutions in the domain of real numbers.

```
x/.

```

Replace `x` with the solutions.

### Alternative version, 35 bytes

```
N@ProductLog[{-1,0},#]~Cases~_Real&

```

Try it online!
> 0 votes

# Answer
# Python 3, 258 bytes

```
e,f,X,R,L=2.7182818,lambda x:x*e**x,float(input()),0,-1
if X>=-1/e:
 while f(R)<X:R+=1
 while f(R)>X:
  M=(L+R)/2
  if f(M)<X:L=M
  else:R=M
 print(M)
 if X<0:
  while f(L)<X:L-=1
  while f(L)!=X:
   M=(L+R)/2
   if f(M)<X:R=M
   else:L=M
  if M!=-1:print(M)

```

Try it online!

A port of my 05AB1E answer
> 0 votes

# Answer
# SageMath, 39 bytes

```
lambda z:[lambert_w(l,z)for l in[0,-1]]

```

Try it on SageCell!
> 0 votes

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


title: Are these states connected?

text:
# Question
Title: Are these states connected?
*With the US election going on right now, I noticed that there is one (completely meaningless, but still) thing which Trump can still achieve and which is out of reach for Biden: Having the won states being connected.*

**Task:** Given a list of strings of two-letter abbreviations (see below) for US states, determine whether they are connected. That is, is the graph whose edges are the states in this list and where two edges are connected whenever the corresponding states are neighbors to each other connected? That is, for each two states, does there exist a path (in this graph) from one to another?

On Githhub, ubikuity has compiled a list of neighboring US states, which I copy here for convenience:

```
AK,WA
AL,FL
AL,GA
AL,MS
AL,TN
AR,LA
AR,MO
AR,MS
AR,OK
AR,TN
AR,TX
AZ,CA
AZ,CO
AZ,NM
AZ,NV
AZ,UT
CA,HI
CA,NV
CA,OR
CO,KS
CO,NE
CO,NM
CO,OK
CO,UT
CO,WY
CT,MA
CT,NY
CT,RI
DC,MD
DC,VA
DE,MD
DE,NJ
DE,PA
FL,GA
GA,NC
GA,SC
GA,TN
IA,IL
IA,MN
IA,MO
IA,NE
IA,SD
IA,WI
ID,MT
ID,NV
ID,OR
ID,UT
ID,WA
ID,WY
IL,IN
IL,KY
IL,MO
IL,WI
IN,KY
IN,MI
IN,OH
KS,MO
KS,NE
KS,OK
KY,MO
KY,OH
KY,TN
KY,VA
KY,WV
LA,MS
LA,TX
MA,NH
MA,NY
MA,RI
MA,VT
MD,PA
MD,VA
MD,WV
ME,NH
MI,OH
MI,WI
MN,ND
MN,SD
MN,WI
MO,NE
MO,OK
MO,TN
MS,TN
MT,ND
MT,SD
MT,WY
NC,SC
NC,TN
NC,VA
ND,SD
NE,SD
NE,WY
NH,VT
NJ,NY
NJ,PA
NM,OK
NM,TX
NM,UT
NV,OR
NV,UT
NY,PA
NY,VT
OH,PA
OH,WV
OK,TX
OR,WA
PA,WV
SD,WY
TN,VA
UT,WY
VA,WV

```

To be clear, “to be a neighbor of” is symmetric and hence the entry `AK,WA` means that AK neighbors WA *and* that WA neighbors AK. There might be some disagreement whether some of these states are indeed neighbors of each other but for the purpose of this question, let us go with the list above. (Although that would mean that Trump needs to lose Alaska in order to have his won states connected.)

**Input:** A list of two-letter strings or something equivalent such as a single string consisting of a series of two-letter pairs such as `"AK WA OR"` or `"AKWAOR"`. It may be assumed that each string is one of the two-letter abbreviations in the list above and that no string appears more than once in the list.

**Output:** Return/Ouput a truthy value if the states are connected and a falsey value if they are not.

(Very!) simple test cases:

* `[]` is connected.
* `["AK"]` is connected.
* `["AK", "WA", "OR"]` is connected.
* `["UT", "CO", "WY", "KS", "NM"]` is connected. (That is, they form a connected graph although they do not form a “line” of neighboring states.)
* `["AK", "OR"]` is not connected.
* `["ID", "OR", "WA", "AL", "GA", "TN"]` is not connected.

Standard I/O rules apply and standard loopholes are forbidden.

This is , so shortest code in bytes wins.

# Answer
> 14 votes
# Wolfram Language (Mathematica), ~~169~~ 167 bytes

```
ConnectedGraphQ@Subgraph[Cases[#[v="StateAbbreviation"]&/@#@"BorderingStates"#@v&/@Interpreter["USState"]@#|"CA""HI"|"AK""WA"/."MI""MN"|"NY""RI"->0,a_ b_:>a<->b,3],#]&

```

Try it online!

TIO doesn't have data sets downloaded, so most of the footer is to ensure the code works as if they had been.

The `BorderingStates` properties differ from the given list of adjacencies in four ways: HI and AK do not border any other states, MI borders MN, and NY borders RI.

```
Interpreter["USStates"]@#           (* get Entitys corresponding to abbreviations *)
#@"BorderingStates"                 (* for each state, get a list of bordering states, *)
#[v="StateAbbreviation"]&/@ % #@v&  (* pair it (unordered) with each of those and convert back to abbreviations. *)
% /@ %%% |"CA""HI"|"AK""WA"         (* append CA-HI and AK-WA, *)
% /."MI""MN"|"NY""RI"->0            (* discard MI-MN and NY-RI, *)
Cases[ % ,a_ b_:>a<->b,3]           (* then get all pairs and convert them to edges. *)
ConnectedGraphQ@Subgraph[ % ,#]&    (* is the subgraph consisting of input states connected? *)

```

---

There's also `GraphData["ContiguousUSAGraph"]`, which is missing AK-WA, AZ-CO, CA-HI, and NM-UT edges. Unfortunately, the vertices are numbered in what seems to be an arbitrary order.

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

Returns a Boolean value.

```
A=>!A.some(s=>s,(g=x=>A.map((s,j)=>'dx5d0w805045081o3klg165343501b328xi342010q4z45v3161r7k0q168i383xe40h3k0e0e3j7f090g6i190x120w621h0oax504lfbqd1b1n9g601l4rbb6o1c0p1v262h6vdy4lac1t561n1f06pnkm443q6jpq845x0u1a1c080y2z3a25112b1q9um81cgs1e041s530abh1k1zksin6d0w'.match(/../g).every(s=>t-=P(s,36),t=(P=parseInt)(x>s?s+x:x+s,36)%22958+1)||g(j),A[x=A[i=x],i]=0))(0))

```

Try it online!

# Answer
> 8 votes
# 05AB1E, <sup>~~207~~ ... ~~194~~</sup> 187 bytes

Thanks to Kevin Cruijssen for -1 byte!
+65 bytes because I had a bug in the generation program and forgot to include quite a few borders.

```
.•K0®Z"E=м7δþˆLäZΩcÉ!P0:n~Žæ₃ƒû‡âQƶºì`tu×^èÂā„∊\¦₁ôβ2Èœ÷Š±TBÀ7Ã•u2ôIkDδ‚εε•AмÎÝ≠ζó'#‚Ó¶–ºÇΘ¶7˜H»«âиÈ8ëf:ÝQº[EÍø’Δ₁#ÍÂ|Q₄T´ƶŽ#UΣMW„é!ʒHµßŠ¸ô7¬·ΔŠ¥Ò÷¾kå«ÛǝO₆ðÿ•51вηOs{R`38*+åyË+]DvDøδ*O}˜ĀP

```

Try it online!

This generates a adjacency matrix \\$A\\$ of the given states and checks if it represents a connected graph using a modified method from this math.se answer. Instead of calculating \\$A^k\\$, we calculate \\$A^{2k}\\$, because it is shorter.
~~For some reason the matrix multiplication code `øδ*O` is really slow, this means that the test case with five states doesn't finish on TIO.~~ *Edit:* The lazy evaluation seems to cause problems here, resulting in extrememly long execution time.

**Commented**:

```
.•K...Ã•u2ôIkDδ‚             # convert from list of abbreviations to matrix of integer pairs
.•K...Ã•                     # push compressed string "mirivaiascaldcoknjmoakmtcapacohidevtkywiinmemanmksilwaorgamnsdidohneflnctnnywywvmsndtxnhctarnvmdutlaaz"
                             # this is the concatenation of all state abbreviations
          u                  # convert to uppercase
           2ô                # split into groups of 2
             Ik              # find the index of the each input in this state list
               D             # duplicate
                δ‚           # and create a matrix of all pairs

εε•A...ÿ•51вηOs{R`38*+åyË+]  # calculate adjacencies
ε                            # map over the rows:
 ε                           # map over the pairs:
  •A...ÿ•51в                 # push compressed integer list [19, 1, ..., 26, 50]
            η                # get all prefixes
             O               # sum every prefix
                             # this list now contains all adjacent states represented as
                             #   a + b*38, where a>b
                             # it also contains some pairs (a, a), this reduces the maximum difference
                             #   between integers, leading to shorter compression in a lower base
              s              # swap to current pair
               {R            # sort and reverse it => [a, b]
                 `           # push both numbers on the stack
                  38*        # multiply b by 38
                     +       # sum both values
                             # this maps a few different pairs of states to the same integers,
                             #  but with the given permutations of states this is fine
                      å      # is this contained in the list?
                       y     # push the pair again
                        Ë    # are all values equal? (is this the same state twice?)
                         +   # sum / boolean or
                          ]  # end both maps
                             # Now the adjacency matrix of the states is on the stack
                             #  ex.: for input ["AK","WA","OR"] this is [[1,1,0],[1,1,1],[0,1,1]]

DgFDøδ*O}˜ĀP                 # check if adjacency matrix is connected
D                            # duplicate the matrix
 v     }                     # for each row square the current matrix M:
  D                          #   duplicate the matrix
   ø                         #   transpose it
    δ                        #   for every pair of rows in M and M^T
     *                       #   multiply element-wise
      O                      #   and sum each list
        ˜                    # flatten the matrix
         Ā                   # Check if every value is not 0
          P                  # take the product / boolean all

```

Try it with step by step output!

# Answer
> 4 votes
# Jelly,  ~~143~~  139 bytes

```
,OṢ*/V%⁽]Ƙ%⁽9ḃ%⁽ðṭe“`€LE<⁼,#g>Q#&68-s¦Ø¬Yḟ¢>ȷ*I¬Þ!Ƈ?øẇ@Þ²m>Ṡ3+@O*c÷©%"*Þ¢Ð⁾ẠþÑẈÐẈ"æ×ḳw³l¢qṠ©|4°€£Ð%½^©Ñ³©Ṇ-N¿ð!ƊẉœK)½ƇØX#²4÷+‘Ä¤ȯ⁼ðþ`æ*L$PẸ

```

A monadic Link accepting a list of lists of characters (valid state abbreviations) which yields `1` if the states are connected or `0` if not.

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

### How?

```
,OṢ*/V%⁽]Ƙ%⁽9ḃ%⁽ðṭe“...‘Ä¤ȯ⁼ðþ`æ*L$PẸ - Link: states
                              `       - use states as both arguments of:
                             þ        -   table using:   (makes an adjacency matrix)
                            ð         -     the dyadic chain, f(A, B):
,                                     -       pair -> [A, B]   e.g. ["HI", "CA"]
 O                                    -       ordinals              [[72, 73], [67, 65]]
  Ṣ                                   -       sorted                [[67, 65], [72, 73]]
    /                                 -       reduce using:
   *                                  -         exponentiation      [300182793244778239701651745925447642838407176218846116477308730441782375736846470235643437821593799141277880459172066217016359091361, 2201278718441498733883192946340630358395332861266884669706285143644864868806820973839329645162232740318586365901865065097808837890625]
     V                                -       evaluate              3001827932447782397016517459254476428384071762188461164773087304417823757368464702356434378215937991412778804591720662170163590913612201278718441498733883192946340630358395332861266884669706285143644864868806820973839329645162232740318586365901865065097808837890625
       ⁽]Ƙ                            -       24399
      %                               -       modulo                12108
           ⁽9ḃ                        -       15482
          %                           -       modulo                12108
               ⁽ðṭ                    -       7225
              %                       -       modulo                4883
                         ¤            -       nilad followed by link(s) as a nilad:
                   “...‘              -       code-page-indices = [96, 12, 76, 69, 60, 140, 44, 35, 103, 62, 81, 35, 38, 54, 56, 45, 115, 5, 18, 7, 89, 235, 1, 62, 26, 42, 73, 7, 20, 33, 144, 63, 29, 246, 64, 20, 130, 109, 62, 205, 51, 43, 64, 79, 42, 99, 28, 6, 37, 34, 42, 20, 1, 15, 142, 171, 31, 16, 187, 15, 187, 34, 22, 17, 217, 119, 131, 108, 1, 113, 205, 6, 124, 52, 128, 12, 2, 15, 37, 10, 94, 6, 16, 131, 6, 180, 45, 78, 11, 24, 33, 145, 227, 30, 75, 41, 10, 144, 18, 88, 35, 130, 52, 28, 43]
                        Ä             -       cumulative sums = [96, 108, 184, 253, 313, 453, 497, 532, 635, 697, 778, 813, 851, 905, 961, 1006, 1121, 1126, 1144, 1151, 1240, 1475, 1476, 1538, 1564, 1606, 1679, 1686, 1706, 1739, 1883, 1946, 1975, 2221, 2285, 2305, 2435, 2544, 2606, 2811, 2862, 2905, 2969, 3048, 3090, 3189, 3217, 3223, 3260, 3294, 3336, 3356, 3357, 3372, 3514, 3685, 3716, 3732, 3919, 3934, 4121, 4155, 4177, 4194, 4411, 4530, 4661, 4769, 4770, 4883, 5088, 5094, 5218, 5270, 5398, 5410, 5412, 5427, 5464, 5474, 5568, 5574, 5590, 5721, 5727, 5907, 5952, 6030, 6041, 6065, 6098, 6243, 6470, 6500, 6575, 6616, 6626, 6770, 6788, 6876, 6911, 7041, 7093, 7121, 7164]
                  e                   -       exists in?            1
                           ⁼          -       (A) equals (B)?       0
                          ȯ           -       logical OR            1
                                  $   - last two links as a monad:
                                 L    -   length
                               æ*     -   matrix power -> Adj^n_states
                                   P  - product -> products of columns
                                    Ẹ - any?

```

All this could be shorter if one manages to find a suitable salt and domain for Jelly's built-in hash atom, , but I don't really know how to find that needle.

# Answer
> 3 votes
# Charcoal, 266 bytes

```
≔Ｅ⪪Ｓ²⟦ι⟧θＦ⪪”}∨ⅉ\`⁸)ιfP≦?OX↙“a:;τ,πC_Ｄβ⁶k4_4÷‽ΦI¹#μＯ⪪ς¶⎇≦↙xh\8ＢＮnkGＭïＴü)﹪▷；⮌Uχγx◧i◧⌊÷iXιh↧υηΠ�Ｅ~*>←ρ↧Ｄ!q⟦⦃№➙U&sU+]I⁹π‹¿ê⁸¤&º⌈ü{³⟦f‽?}Ｏ/ＱＺ7·Ｊ＆ＭＤＬnueÞW≕*"eε§ºＲ0q&ＲGTwbDLFＳ⁸~,*➙Ｊ↨a…⁷{¤[ε↖=ＤC⊞SＳ⌈BφＷ¦ï?ⅉIêＥχ⌊±±3 ·ι.×qShiδiＺyZ¤d↨Ｃζⅈr⪪Hσ ωＷJ”⁴ＦΦθ№κ…ι²ＦΦ⁻θ⟦κ⟧№λ✂ι²Ｗλ⊞κ⊟λ›²ＬΦθι

```

Try it online! Link is to verbose version of code. Takes input as a string of two-letter pairs. Note that Charcoal requires a trailing newline to identify an empty string. Output is a Charcoal boolean, i.e. `-` for connected, nothing for disconnected. Explanation:

```
≔Ｅ⪪Ｓ²⟦ι⟧θ

```

Split the input into states and create a list for each state.

```
Ｆ⪪”....”⁴

```

Split the compressed adjacency list into individual entries and loop over them.

```
ＦΦθ№κ…ι²

```

Loop over any entries in the input list that contain the first adjacent state.

```
ＦΦ⁻θ⟦κ⟧№λ✂ι²

```

Loop over any other entries in the input list that contain the second adjacent state.

```
Ｗλ⊞κ⊟λ

```

Merge all the states from the adjacent entry.

```
›²ＬΦθι

```

Check that there is only one list of states left.

# Answer
> 3 votes
# Python 2, ~~632~~ ~~596~~ ~~550~~ ~~549~~ ~~545~~ 550 bytes

It's long but it works.

-36: Use regex and remove , and ; from compressed string (@nthnchu)

-46: Shorten for loops, compress lists (@ovs)

-1: Change `print(len(i)==0)` to `print len(i)==0` (@nthnchu)

-4: Change `len(i)==0` to `i==[]` (@nthnchu)

+5: Fix for `[]` by replacing `f(i[0])` with `if i:f(i[0])` (@nthnchu)

```
import re
i=input()
l=[re.findall('..',x)for x in re.findall("....","eJwVj2GyAyEIg8+WUdulCuwoi7X3P8jL+/FNECIa9A2M18B4U3VhhGEOYKqThekd878XX/wKiONnShK/JwouKbAs8Fm8r+LWiBb3Xpxz36eEooRRp9SitZZEbdRmn9puvPj2G1beWCRMIEOgVHWBNcGqgi1SNaRaSnUuelhvkEO3yehU+gd9xtqU6ldfyl9Z68t7P6wPeyfoSPSzc0DXQHwVdpGjmKLI0HpDa5Kd2jgTJ1vUrKotwppZlTnVw3SR4Cw4i32srGIMbcxqdVVr/7B/ZdjHjn1uGL/DS1/TJyx9WlIP+yfDrxt+7fQeX58bN3YuZqURD/cnz3+qZoSc".decode("base64").decode("zip"))]
def f(s):i.remove(s);[f(a)for a in[a[1-a.index(s)]for a in l if s in a]if a in i]
if i:f(i[0])
print i==[]

```

Try it online!

# Answer
> 2 votes
# Red, 647 bytes

```
func[b][
s:{AKWA ALFLGAMSTN ARLAMOMSOKTNTX AZCACONMNVUT CAHINVOR COKSNENMOKUTWY CTMANYRI DCMDVA DEMDNJPA FLGA GANCSCTN IAILMNMONESDWI IDMTNVORUTWAWY ILINKYMOWI INKYMIOH KSMONEOK KYMOOHTNVAWV LAMSTX MANHNYRIVT MDPAVAWV MENH MIOHWI MNNDSDWI MONEOKTN MSTN MTNDSDWY NCSCTNVA NDSD NESDWY NHVT NJNYPA NMOKTXUT NVORUT NYPAVT OHPAWV OKTX ORWA PAWV SDWY TNVA UTWY VAWV}m:
copy#()foreach a split s sp[t: parse a[collect any[keep 2 skip]]u: take t
either m/:u[append m/:u t][put m u t]foreach v t[either m/:v[append m/:v u][put
m v to[]mold u]]]r: on if 1 < length? b[foreach a b[r: r and series?
find collect[d: copy b alter d a foreach e d[keep m/:e]]a]]r]

```

Try it online!

This is a horribly long and naive solution...

---
Tags: code-golf, graph-theory
---


title: Knight on the Rim is Grim

text:
# Question
Title: Knight on the Rim is Grim
# Introduction

Aron Nimzowitsch was a leading chess master and a influential chess writer.

In his book 'My System', the first chapter deals about the importance of the center and why you should dominate it. The simple reason is that your pieces have more possible direct next moves when being in the center which again gives the player more power.

This gets very clear when looking at different positions of a knight and its potential next moves (shown in pink) on an empty board:

# Objective

Evaluate the number of potential direct next moves of a knight on an empty board based on its position.

# Input Specs

The position of the knight.

First the x (column) and then the y (row). `0 0` is the left bottom corner.

For simplicity, I changed the labels of a chess board to numbers only. For our examples and test cases we use a 0-based index, you are free to use a 1-based index though.

You can use any type of possible input formats, an array, function arguments, etc.

# Output Specs

The number of potential direct next moves for a knight on an empty board.

# Test Cases

```
3 4 => 8
4 6 => 6
7 7 => 2
1 0 => 3

```

*Test cases are employing a 0-based index.* The full grid of values is:

```
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

```

# Answer
> 25 votes
# Python 2, 35 bytes

```
lambda x,y:50/(8+x*x/7-x+y*y/7-y)-4

```

Try it online!

---

**Python 2, 39 bytes**

```
lambda x,y:50/(8-x*(7-x)/5-y*(7-y)/5)-4

```

Try it online!

Takes inputs 0-indexed.

The expression `x*(7-x)/5` takes the coordinate values `0..7` to

```
[0, 1, 2, 2, 2, 2, 1, 0]

```

(`min(x,7-x,2)` does the same, but is longer.) Summing this for `x` and `y` gives the right pattern but with the wrong numbers

```
0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

```

(See Neil's solution for better reasoning as to why this gives about the right pattern.)

Finally, the mapping `a -> 50/(8-a)-4` with floor-division gives the right values

```
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

```

An alternative equally-long solution with 1-indexed inputs:

```
lambda x,y:(x*(9-x)/6+y*(9-y)/6)**2/6+2

```

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

*Thanks to @Neil for 1 byte off!*

```
8:HZ^ZP5X^=s

```

Input is 1-based.

**Try it online!**

### Explanation

This computes the Euclidean distance from the input to each of the 64 positions in the chessboard, and finds how many of those values equal the square root of 5.

Since the coordinates are integer values, we can be sure that the two floating-point values representing the square root of 5 (that computed from the coordinates and that computed directly) are indeed the same.

```
8:      % Push array [1 2 ... 8]
H       % Push 2
Z^      % Cartesian power. Gives 2D array [1 1; 1 2; ... 1 8; 2 1; ... 8 8]
ZP      % Implicit input. Compute Euclidean distances, considering each row as a point
5X^     % Square root of 5
=s      % Compute how many squared distances equal sqrt(5). Implicit display

```

# Answer
> 15 votes
# Mathematica ~~63~~ 43 bytes

With 20 bytes saved thanks to suggestions by Martin Ender!

```
EdgeCount[8~KnightTourGraph~8,#+1+8#2/<->_]&

```

The above finds the number of squares that are 1 hop away from the given cell on the complete knights tour graph.

---

`g=KnightTourGraph[8,8,VertexLabels->"Name",Axes->True]`

displays the complete knight's tour graph, with vertex names and coordinates. Note that Mathematica defaults to one-based indexing for the coordinates.

---

`#+1+8#2&[r,f]` converts returns the vertex corresponding to square at rank (row), `r`, and file (column), `f`, using zero-based values as input.

For example `#+1+8#2&[2,1]` returns 11.

---

`EdgeCount` gives the number of edges in the neighborhood graph.

---

The edges for rank 2, file 1 (square 11):

```
IncidenceList[8~KnightTourGraph~8, 8 #2 + # + 1] &[2, 1]

(*{1 <-> 11, 5 <-> 11, 11 <-> 17, 11 <-> 21, 11 <-> 26, 11 <-> 28}*)

```

The highlighted edges:

```
HighlightGraph[g, {1, 5, 11, 17, 21, 26, 28, Style[1 <-> 11, Thick, Blue], Style[5 <-> 11, Thick, Blue], Style[11 <-> 17, Thick, Blue], Style[11 <-> 21, Thick, Blue], Style[11 <-> 26, Thick, Blue], Style[11 <-> 28, Thick, Blue]},GraphHighlightStyle -> "DehighlightFade", PlotRangePadding -> .5]

```

---

**Method 2: Euclidean distance**

70 bytes

This method is longer, but possibly of some interest. The approach is to check the Euclidean distance between the center of the chessboard and the cell of interest.

```
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&

```

---

Exemplifying

```
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{0, 0}
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{3, 3}

```

2

8

---

To help visualize how the distance from the center of the chessboard is sufficient for assigning a value.

```
values={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};
f[x_]:=Text[x,#]&/@Position[values,x]r_~w~p_:=RegionMember[{3.5`,3.5`}~Disk~r,p]
h@y_:=Which[2.2~w~y,8,3~w~y,6,4~w~y,4,4.6~w~y,3,2<3,2]

Graphics[{Circle[{4.5, 4.5}, 2.3], Circle[{4.5, 4.5}, 3],

```

Circle\[{4.5, 4.5}, 4\],

Circle\[{4.5, 4.5}, 4.6\], Flatten\[f /@ {2, 3, 4, 6, 8}, 1\]}, Axes -\> True, AxesOrigin -\> {-1, -1}\]

---

The numbers 2.2, 3, 4, and 4.6 are the radii of the circles.

# Answer
> 12 votes
## JavaScript (ES6), 38 bytes

```
(x,y)=>+"23468"[((7-x)*x+(7-y)*y)/5|0]

```

Takes 0-indexed inputs. Explanation: Look at the squares of the distances to the centre:

```
24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5

```

The number of reachable squares falls into five bands:

```
8    0-5
6    5-10
4   10-15
3   15-20
2   20-25

```

I actually calculate 24.5 - (3.5 - x) \** 2 - (3.5 - y) \** 2 = (7 - x) * x + (7 - y) * y as it's a shorter calculation, but all it does is reverse the order of the bands.

# Answer
> 11 votes
# Jelly, 10 bytes

```
8ṗ2_³²S€ċ5

```

1-indexed. Takes a single argument of the form `[x,y]`. Try it here.

```
8ṗ2          Cartesian square [[1,1],[1,2]…[8,8]]
   _³        Subtract the input
     ²S€     Compute the norm of each vector
        ċ5   Count fives

```

Dennis saved a byte!

# Answer
> 8 votes
## Mathematica, ~~44~~ 40 bytes

I've currently got three solutions at the same byte count:

```
2[3,4,6,8][[Tr@⌊3.2-.8Abs[#-4.5]⌋]]&
Tr@⌈.85(4-Abs[#-4.5])⌉/.{5->6,6->8}&
⌊Tr@⌈.85(4-Abs[#-4.5])⌉^1.1608⌋&

```

All of those are unnamed functions that take pair of coordinates like `{3, 4}`, which are 1-based.

I tried coming up with a somewhat explicit formula. The general pattern on the entire board looks like this:

The actual values of those colours (from lightest to darkest) are `2, 3, 4, 6, 8`. That is:

```
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

```

We first exploit the symmetry by shifting the origin to the centre, taking the absolute value and subtracting the result from `4`. This gives us coordinates `0.5` to `3.5` increasing from each corner. In order to make the centre coordinates the same we need to map `0.5` and `1.5` to different values and `2.5` and `3.5` to the same value. This is easily done by multiplying by `0.8` (gives`{0.4, 1.2, 2., 2.8}`) and flooring the result. So now we've got `{0, 1, 2, 2}` as distances from the centre. If we add up the coordinates in each cell, we get this table:

```
0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

```

This has unique values for all the different possible results, so we simply use it as an index into `2[3,4,6,8]`.

In the second version we use ceiling instead floor. This way, `2`, `3` and `4` are already correct, but we get `5` and `6` instead of `6` and `8`, so we correct those manually with a substitution rule.

Finally, in the third version, we extend `5` and `6` upwards to `6` and `8` by means of exponentiation, followed by another floor operation.

# Answer
> 6 votes
# Java - ~~160~~ 150 bytes

```
int m(int r,int c){int m=0,i,j;for(i=0;i<3;i+=2)for(j=0;j<3;j+=2){m+=r+i>0&r+i<9&c+2*j>1&c+2*j<11?1:0;m+=r+2*i>1&r+2*i<11&c+j>0&c+j<9?1:0;}return m;}

```

Ungolfed:

```
public static int m(int r, int c) {
    int m=0;
    for(int i=-1;i<2;i+=2)
        for(int j=-1;j<2;j+=2){
            m += r+i>-1 && r+i<8 && c+2*j>0 && c+2*j<8 ? 1:0;
            m += r+2*i>0 && r+2*i<8 && c+j>1 && c+j<8 ? 1:0;
        }
    return m;
}

```

The ungolfed code is identical except for changing the bounds of the for loop to save 4 bytes. Works by iterating through each possible move and performing a bounds check (\>0 and \<8). Uses the fact that the offsets are (1, 2), (2, 1), (-1, 2), (-2, 1), etc. and is able to check 2 moves for each value of i and j.

Edit: 10 bytes saved thanks to suggestions by Leaky Nun and u902383.

# Answer
> 6 votes
## APL, 21 chars

```
{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}

```

In English:

* `(⍳8 8)`: 8x8 rank-2 array containing the coordinates of all the cells;
* `+/¨×⍨(⍳8 8)-⊂⍵`: square of the euclidean distances of the given cell with respect to every cell on the board;
* `5=`: matrix of 0/1, where the 1s appear at squared distances equal 5;
* `+/,`: sum the flattened matrix

Test (in origin 1):

```
    f←{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}
    f¨1+(3 4)(4 6)(7 7)(1 0)
8 6 2 3

```

In this form:

```
f←{+/,5=+/¨×⍨(⍳⍺)-⊂⍵}

```

the left argument can specify the dimensions of the board. Hence `8 8 f` will work for the standard square chessboard. But on a larger and rectangular board, the test cases would give different results. For instance, on a 12x10 board:

```
    g←(10 12)∘f
    g¨1+(3 4)(4 6)(7 7)(1 0)
8 8 8 3

```

# Answer
> 6 votes
# C, 44 Bytes

```
f(x,y){return "23468"[((7-x)*x+(7-y)*y)/5];}

```

But this is better:

```
f(x,y){return "2344443234666643468888644688886446888864468888643466664323444432"[x*8+y];}

```

# Answer
> 5 votes
## Haskell, ~~49~~ 48 bytes

```
w=[0..7]
x%y=sum[1|a<-w,b<-w,(a-x)^2+(b-y)^2==5]

```

# Answer
> 5 votes
# Java, 81 characters (113 bytes)

```
int r(int a,int b){return "⍄䐲㑦晃䚈衤䚈衤䚈衤䚈衤㑦晃⍄䐲".codePointAt(a*2+b/4)>>(3-b%4)*4&15;}

```

Encode the whole result table as unicode table and then get appropriate bytes doing bitwise operations.

You can see it online here: https://ideone.com/K9BojC

# Answer
> 3 votes
# Python, 94 bytes

```
lambda x,y,a=[2,1,-1,-2,-2,-1,1,2]:list((9>x+a[i]>0)&(9>y+a[5-i]>0)for i in range(8)).count(1)

```

Uses 1 based indexing.

Demo at https://repl.it/C6gV.

# Answer
> 2 votes
# Pyth - ~~33~~ 15 bytes

*Thanks to @LeakyNun for reducing my size by half.*

Rearranging the maps and `V`'s will probably lemme golf a little off.

```
/sM*Fm^R2-Rd8Q5

```

Test Suite.

# Answer
> 2 votes
# APL (Dyalog Unicode), 15 bytesSBCS

```
≢⍸2=|×.-∘⎕¨⍳8 8

```

Try it online!

# Answer
> 2 votes
# , 23 bytes

```
1#.1#.5=[:+&*://]-/i.@8

```

Try it online!

Homage to Lynn's method, converted to J

# Answer
> 1 votes
## Actually, 18 bytes

```
`;7-2km`MΣ8-:50\¬¬

```

Try it online!

This implements the same formula that many other answers have been using: `50/(8-x*(7-x)//5+y*(7-y))//5)-4`. Input is taken as a list: `[x,y]` (or any iterable literal in Python, like `(x,y)` or `x,y`).

Explanation:

```
`;7-2km`MΣ8-:50\¬¬
`;7-2km`M           for each value in input:
 ;7-                  make a copy, subtract from 7
    2                 push 2
     km               minimum of the three values (x, 7-x, 2)
         Σ          sum
          8-        subtract from 8
            :50\    integer divide 50 by the value
                ¬¬  subtract 2 twice

```

# Answer
> 0 votes
# Perl 6, 44 bytes

```
{+grep {5==[+] $_>>²},((^8 X, ^8)XZ-(@_,))}

```

Try it online!

# Answer
> 0 votes
# Forth (gforth), 49 bytes

```
: g 9 over - 6 */ ;
: f g swap g + dup 6 */ 2 + ;

```

Try it online!

Port of xnor's 1-based solution. `f` takes `x y` (1-based) on the stack and computes `(x(9-x)/6 + y(9-y)/6)**2/6+2`. Uses the built-in `*/` to do a multiplication followed by division at once and save a space.

```
: g ( x -- x(9-x)/6 )
  9 over -  \ ( x 9-x )
  6 */      \ x*(9-x)/6
;

: f ( x y -- ans )
  g swap g    \ apply g to y, then to x
  + dup 6 */  \ (gx+gy)*(gx+gy)/6
  2 +
;

```

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


title: 5, 2, 16, 3580, What comes next?

text:
# Question
Title: 5, 2, 16, 3580, What comes next?
Consider the positive integer powers of five in decimal. Here are the first 25, right aligned:

```
 X                5^X
 1                  5
 2                 25
 3                125
 4                625
 5               3125
 6              15625
 7              78125
 8             390625
 9            1953125
10            9765625
11           48828125
12          244140625
13         1220703125
14         6103515625
15        30517578125
16       152587890625
17       762939453125
18      3814697265625
19     19073486328125
20     95367431640625
21    476837158203125
22   2384185791015625
23  11920928955078125
24  59604644775390625
25 298023223876953125

```

Notice that the rightmost column of the powers is all `5`'s. The second column from the right is all `2`'s. The third column from the right, read from top to bottom, alternates `1`, `6`, `1`, `6`, etc. The next column starts `3`, `5`, `8`, `0` and then cycles.

In fact, every column (if we go down far enough) has a cycling sequence of digits whose length is twice that of the previous cycle, except for the initial `5`'s and `2`'s cycles.

Calling N the column number, starting with N = 1 at the right, the first few cycles are:

```
N cycle at column N
1 5
2 2
3 16
4 3580
5 17956240
6 3978175584236200
7 19840377976181556439582242163600
8 4420183983595778219796176036355599756384380402237642416215818000

```

# Challenge

Given a positive integer N, output the decimal digits of the cycle at column N, as described above. For example, the output for N = 4 would be `3580`.

The digits may be output as a list such as `[3, 5, 8, 0]` or in another reasonable format so long as:

* The digits are in order as read from top to bottom in the power columns. e.g. `0853` is invalid.
* The cycle starts with the top number in its power column. e.g. `5803` is invalid as the 4th column starts with `3` not `5`.
* Exactly one cycle is output. e.g. `358` or `35803` or `35803580` would all be invalid.

Your code must work for at least N = 1 through 30.

If desired you may assume the columns are 0-indexed instead of 1-indexed. So N = 0 gives `5`, N = 1 gives `2`, N = 2 gives `16`, N = 3 gives `3580`, etc.

**The shortest code in bytes wins**.

Thanks to Downgoat and DJ for challenge support.

# Answer
> 28 votes
# Python 2, ~~62~~ ~~61~~ 58 bytes

Zero-based. I assume the L suffixes are acceptable.

```
lambda n:[5**(n*3/7-~i)/2**n%10for i in range(2**n/2or 1)]

```

Output:

```
0 [5]
1 [2]
2 [1, 6]
3 [3, 5, 8, 0]
4 [1, 7, 9, 5, 6, 2, 4, 0]
5 [3, 9, 7, 8, 1, 7, 5, 5, 8, 4, 2, 3, 6, 2, 0, 0]
6 [1, 9, 8, 4, 0, 3, 7, 7, 9, 7, 6, 1, 8, 1, 5, 5, 6, 4, 3, 9, 5, 8, 2, 2, 4, 2L, 1L, 6L, 3
L, 6L, 0L, 0L]
7 [4, 4, 2, 0, 1, 8, 3, 9, 8, 3, 5, 9, 5, 7, 7, 8, 2, 1, 9, 7, 9, 6, 1, 7, 6L, 0L, 3L, 6L,
3L, 5L, 5L, 5L, 9L, 9L, 7L, 5L, 6L, 3L, 8L, 4L, 3L, 8L, 0L, 4L, 0L, 2L, 2L, 3L, 7L, 6L, 4L,
 2L, 4L, 1L, 6L, 2L, 1L, 5L, 8L, 1L, 8L, 0L, 0L, 0L]

```

Previous solution:

```
lambda n:[5**int(n/.7-~i)/10**n%10for i in range(2**n/2or 1)]
lambda n:[str(5**int(n/.7-~i))[~n]for i in range(2**n/2)]or 5

```

---

Explanation:

```
def f(n):
    r = max(2**n / 2, 1)
    m = int(n/0.7 + 1)
    for i in range(r):
        yield (5**(m+i) / 10**n) % 10

```

The `range(2**n/2)` uses the observation that each cycle has length r = 2n-1 except when n = 0, so we just compute the n-th digits for 5m to 5m + r - 1.

The start of the cycle 5m is the first number larger than 10n. Solving 5m ≥ 10n gives m ≥ n / log10 5. Here we approximate log10 5 ≈ 0.7 which will break down when n = 72. We could add more digits to increase the accuracy:

```
| approximation             | valid until        | penalty   |
|---------------------------|--------------------|-----------|
| .7                        | n = 72             | +0 bytes  |
| .699                      | n = 137            | +2 bytes  |
| .69897                    | n = 9297           | +4 bytes  |
| .698970004                | n = 29384          | +8 bytes  |
| .6989700043               | n = 128326         | +9 bytes  |
| .6989700043360189         | too large to check | +15 bytes |
| import math;math.log10(5) | same as above      | +23 bytes |

```

The `/ 10**n % 10` in the loop simply extract the desired digit. Another alternative solution uses string manipulation. I used the trick `~n == -n-1` here to remove 1 byte.

An mentioned in the comment, the expression `5**(m+i) / 10**n` can further be simplified this way, which gives the current 58-byte answer.

(The division `x/2**n` can be done using bitwise right-shift `x>>n`. Unfortunately, due to Python's operator precedence this does not save any bytes.) The fraction 3/7 can also be improved in similar mannar:

```
| approximation                   | valid until         | penalty   |
|---------------------------------|---------------------|-----------|
| n*3/7                           | n = 72              | +0 bytes  |
| n*31/72                         | n = 137             | +2 bytes  |
| n*59/137                        | n = 476             | +3 bytes  |
| n*351/815                       | n = 1154            | +4 bytes  |
| n*643/1493                      | n = 10790           | +5 bytes  |
| n*8651/20087                    | n = 49471           | +7 bytes  |
| int(n*.43067655807339306)       | too large to check  | +20 bytes |
| import math;int(n/math.log2(5)) | same as above       | +26 bytes |

```

# Answer
> 10 votes
# dc, 72 bytes

```
[3Q]sq2?dsa^1+2/dsusk[Ola^/O%plk1-dsk1>q]sp1[d5r^dOla^<psz1+d4/lu>t]dstx

```

0-based indexing.

This uses exact integer arithmetic -- no logarithm approximations. It will work up to the memory capacity of the computer.

Try the dc program online!

---

The dc code can be turned into a Bash solution:

# Bash \+ GNU utilities, ~~96~~ ~~77~~ 75 bytes

```
u=$[(2**$1+1)/2]
dc -e "[O$1^/O%p]sp1[d5r^dO$1^<psz1+d4/$u>t]dstx"|head -$u

```

Try the Bash version online!

# Answer
> 9 votes
# Mathematica, ~~66~~ ~~60~~ 52 bytes

```
Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/.7]/10^#,10]&

```

Anonymous function, 0-indexed. Uses approximation of log5(10) (≈ 0.7)

### How it works?

```
Range@Max[2^#/2,1]

```

Take larger of 2^(input)/2 and 1. Generate {1..that number}

```
...+#/.7

```

Add input/.7

```
5^Floor[...]/10^#

```

Raise 5 to the power of the result (generating powers of 5), divide by 10^input (getting rid of digits to the right of the desired column)

```
Mod[ ...,10]

```

Apply modulo 10, taking the one's digit (the desired column).

### Exact version, 58 bytes

```
Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/5~Log~10]/10^#,10]&

```

# Answer
> 5 votes
# JavaScript (ES7), ~~78~~ 76 bytes

```
f=(N,z=5,s,X=2**N,q=z/10**N|0)=>s|q?X>0?q+f(N,z*5%10**-~N,1,X-2):"":f(N,z*5)

```

0-indexed, i.e. `f(0)` gives `2`.

### Test snippet

```
f=(N,z=5,s,X=1<<N,q=z/Math.pow(10,N)|0)=>s|q?X>0?q+f(N,z*5%Math.pow(10,-~N),1,X-2):"":f(N,z*5)

for (let i = 0; i < 10; i++) console.log(`f(${i}):`, f(i));
```

The snippet uses `Math.pow` instead of `**` for cross-browser compatability.

# Answer
> 4 votes
# CJam, 35

```
5ri(:N.7/i)#2N(#mo{_AN#/o5*AN)#%}*;

```

Try it online

It is space-efficient and not exceedingly slow, took several minutes for input 30 on my computer (using the java interpreter).

# Answer
> 3 votes
# Jelly, ~~26~~ 21 bytes

-2 bytes using kennytm's **0.7** approximation idea

```
2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵

```

**Try it online!** (times out for **n\>15**)

Returns a list of integers, the digits.
Zero based. Theoretically works for **n\<=72** (replace `.7` with `5l⁵¤`, to get floating point accuracy).

### How?

```
2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵ - Main link: n
2*                    - 2 raised to the power of n
  H                   - halved: 2 raised to the power of n-1
   Ċ                  - ceiling: adjust 2**-1 = 0.5 up to 1 for the n=0 edge case
    R                 - range: [1,2,...,ceiling(2**(n-1))] - has length of the period
         $            - last two links as a monad:
      ÷.7             -     divide by 0.7 (approximation of log(5, 10), valid up to n=72)
     +                - add (vectorises)
          Ḟ           - floor (vectorises)
             5        - 5
           *@         - exponentiate (vectorises) with reversed @arguments
                  ¤   - nilad followed by link(s) as a nilad
               ⁵      -     10
                 ⁸    -     left argument, n
                *     -     exponentiate: 10 raised to the power of n
              :       - integer division: strips off last n digits
                   %⁵ - mod 10: extracts the last digit

```

*Locally:* the working set memory for **n=17** climbed to around **750MB** then spiked to around **1GB**; for **n=18** it slowly reached **2.5GB** then spiked to around **5GB**.

# Answer
> 3 votes
# Perl 6, 52 bytes

```
->\n{(map {.comb[*-n]//|()},(5 X**1..*))[^(2**n/4)]}

```

Works for arbitrarily high inputs, given sufficient memory *(i.e. no logarithm approximation)*.
Returns a list of digits.

Try it online!

### How it works

```
->\n{                                              }  # A lambda with argument n.
                            (5 X**1..*)               # The sequence 5, 25, 125, 625...
      map {               },                          # Transform each element as such:
           .comb[*-n]                                 #   Extract the n'th last digit,
                     //|()                            #   or skip it if that doesn't exist.
     (                                 )[^(2**n/4)]   # Return the first 2^(n-2) elements.

```

The "element skipping" part works like this:

* Indexing a list at an illegal index returns a Failure, which counts as an "undefined" value.
* `//` is the "defined or" operator.
* `|()` returns an empty Slip, which dissolves into the outer list as 0 elements, essentially making sure that the current element is skipped.

The edge-case `n=1` works out fine, because `2**n/4` becomes `0.5`, and `^(0.5)` means `0 ..^ 0.5` a.k.a. "integers between 0 (inclusive) and 0.5 (not inclusive)", i.e. a list with the single element 0.

# Answer
> 2 votes
# J, 50 bytes

```
(2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]

```

Note: must pass in extended number

Usage:

```
   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580

```

# Answer
> 2 votes
# Haskell, 73 bytes

```
f 0="5"
f n=take(2^(n-1))[reverse x!!n|x<-show<$>iterate(*5)1,length x>n]

```

Try it online! Uses 0-indexing.

**Explanation:**

```
f 0="5"              -- if the input is 0, return "5"
f n=                 -- otherwise for input n
  take(2^(n-1))      -- return the first 2^(n-1) elements of the list
    [reverse x!!n    -- of the nth column of x
      |x<-show<$>    --    where x is the string representation
        iterate(*5)1 --    of the elements of the infinite list [5,25,125,...]
      ,length x>n    -- if x has at least n+1 columns
    ]                -- this yields a list of characters, which is equivalent to a string

```

# Answer
> 1 votes
## Batch, 294 bytes

```
@echo off
if %1==1 echo 5
set/a"l=1<<%1-2,x=0,s=1
set t=
for /l %%i in (2,1,%1)do call set t=%%t%%x
:l
if %l%==0 exit/b
set t=%s%%t%
set s=
set c=
:d
set/ac+=%t:~,1%*5,r=c%%10,c/=10
set s=%s%%r%
set t=%t:~1%
if "%t%"=="" echo %r%&set/al-=1&goto l
if %c%%t:~,1%==0x goto l
goto d

```

Outputs each digit on its own line. Works by calculating the powers of 5 longhand, but only works up to `N=33` due to using 32-bit integers to keep count of how many digits to print. `s` contains the (reversed) last `N` digits of the current power of 5, while `t` contains `x`s used as padding, although the `x=0` makes them evaluate as zero when the next power is calculated. Example for `N=4`:

```
s   t
1   xxx (initial values before the first power of 5 is calculated)
5   xxx
52  xx
521 x
526 x
5213    (print 3)
5265    (print 5)
5218    (print 8)
5260    (print 0)

```

# Answer
> 1 votes
## JavaScript (ES6), 73 bytes

1-indexed. Slightly shorter than the ES7 answer, but fails 3 steps earlier (at N=13).

```
n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

```

### Demo

```
let f =

n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))
console.log(f(7))
console.log(f(8))
```

# Answer
> 0 votes
# PHP\>=7.1, 104 Bytes

```
for($s=1;$i++<2**(-1+$a=$argn);)~($s=bcmul($s,5))[-$a]?$g.=$s[-$a]:0;echo substr($g,0,max(2**($a-2),1));

```

PHP Sandbox Online

# Answer
> 0 votes
# Husk, 15 bytes

```
!z↑+ḋ3İ2Tmod↔İ5

```

Try it online! or Verify first 10 values

## Explanation

```
!z↑+ḋ3İ2Tmod↔İ5
             İ5 list of powers of 5
         mod↔   reverse each and convert to digits
        T       transpose to get repeating columns
 z↑             zip with take using:
   +ḋ3İ2        powers of 2 with [1,1] added
!               return the nth element

```

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