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

Question

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 1

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 = 2^n-1 except when n = 0, so we just compute the n-th digits for 5^m to 5^{m + r - 1}.

The start of the cycle 5^m is the first number larger than 10ⁿ. Solving 5^m ≥ 10ⁿ gives m ≥ n / log₁₀ 5. Here we approximate log₁₀ 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 2

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 3

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 4

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 5

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 6

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 7

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 8

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 9

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 10

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 xs 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 11

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 12

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