# Output the smallest powers of 2 with two identical sub-strings of digits n long

For each integer n, 0 or higher, output the lowest power of 2 that has two identical sub-strings of n digits in decimal, and the two indices where the digit sub-strings start (0-based).

n      Output      Proof (don't output this)
0 => 0 [0 1]        (_1 & 1_)
1 => 16 [0 4]      (65536 & 65536)
1 => 16 [1 2]      (65536 & 65536)
2 => 24 [0 6]      (16777216 & 16777216)
2 => 24 [2 3]      (16777216 & 16777216)

The possible outputs for the first three inputs are given above. When there is more than one output for a given input, either is acceptable. Only the digit positions will be different. Just output the numbers, the brackets are for clarity only. You don't need to output n.

Output a list of as many as you can find in one minute, or your code runs out of resources, whichever comes first. Please include the output with your answer. If the list is huge, just restrict it to the first and last 5. Your code must be able to find up to n = 9 in under a minute. I've written a Perl program that finds n = 9 after about 20 seconds, so this should be easy to do.

Your code doesn't need to halt itself. It is acceptable if you manually break out if it after a minute.

This is , so lowest number of bytes wins!

• I don't get it, should we output only the lowest power of 2, or as many as we can find in one minute? Commented Feb 16, 2016 at 8:26
• @CJDennis Should we time it ourself (and halt it) or we can just let it run? Commented Feb 16, 2016 at 8:33
• It's not clear if this challenge is a code-golf or fastest-code. If you want to keep the primary winning criterion as code-golf, you might want to make a certain speed goal a validity criterion instead (e.g. must return an answer for n = 10 in less than one minute). Commented Feb 16, 2016 at 11:48

# APL (Dyalog Extended), 68 bytes

'01'(0{x≢∪x←⍺⍺,/⍺:⍺((⍺⍺+1)∇∇)⊃⎕←⍵,⊃a/⍨</¨⊢a←⍸∘.≡⍨x⋄(+⌂big⍨⍺)∇1+⍵})0


Try it online!

APL is not known for big integer arithmetic, infinite output, or interpreter speed (and using Extended incurs even more overhead), yet it outputs successfully up to n=9 barely under a minute.

### How it works

The code is basically an infinitely running recursive operator. The left argument is the string representation of the power of 2, the right argument is the corresponding exponent (which was needed to meet the speed requirement), and the left operand is the current value of n.

{
x←⍺⍺,/⍺          ⍝ Extract length-n segments of given number
x≢∪x:           ⍝ If it has duplicates...
a←⍸∘.≡⍨x         ⍝   Construct the pairs of indices of equal slices
⊃a/⍨</¨⊢a        ⍝   Keep the ones (L,R) where L<R and take the first one
⊃⎕←⍵,...         ⍝   Concat with the exponent, print it, extract ⍵ back
⍺((⍺⍺+1)∇∇)...   ⍝   Continue running with n+1
⋄                ⍝ Otherwise...
(+⌂big⍨⍺)∇1+⍵    ⍝   Recurse with next power of two, using same n implicitly
}
'01'(0{...})0  ⍝ Invoke the dop with starting values


# Mathematica, 109 bytes

f@n_:={NestWhile[#+1&,0,Length[p=Position[#,#&@@Commonest@#,1,2]-1]&@Partition[IntegerDigits[2^#],n,1]<2&],p}


n    output
0    {0, {{0},{1}}}
1    {16, {{0},{4}}}
2    {24, {{0},{6}}}
3    {41, {{8},{9}}}
4    {73, {{10},{18}}}
5    {130, {{14},{17}}}
6    {371, {{8},{52}}}
7    {875, {{68},{101}}}
8    {2137, {{12},{240}}}
9    {2900, {{270},{355}}}
10   {7090, {{803},{1123}}}
11   {12840, {{1672},{3185}}}

• I don't know Mathematica very well, so if you can save some bytes by removing some braces in the output, by all means do so. Commented Feb 16, 2016 at 8:33
• @CJDennis Actually, that's the natural expression. I didn't add these braces intentionally. Commented Feb 16, 2016 at 8:37
• @njpipeorgan isn't your program wrong at least for n=3? I think 2^41=2199023255552, which mean the part found by your program is actually 555 and it overlapse with itself. Commented Feb 16, 2016 at 9:33
• @Katenkyo 2199023255552 overlaps with 2199023255552 Commented Feb 16, 2016 at 9:37
• @njpipeorgan nevermind, just saw overlapping matches are authorized... Which totally invalidate what i was working on. Commented Feb 16, 2016 at 9:40

# Python2, 137 119 bytes

It's pretty straightforward:

i=m=0
while 1:
n=2**i
for k in range(len(n)-m+1):
q=n.find(n[k:k+m],k+1)
if-1<q:print i,k,q;m+=1;break
else:i+=1


and the output:

n   output
0   0 0 1
1   16 0 4
2   24 0 6
3   41 8 9
4   73 10 18
5   130 14 17
6   371 8 52
7   875 68 101
8   2137 12 240
9   2900 270 355
10  7090 803 1123


18 bytes saved by btwlf

• Welcome, I'm new here too. Trying to find a better solution with if substring in string I figured out some issues which could enhance your bytescore. Firstly str() may be replaced by backticks, see here. Secondly you missed, that p always equals k. Commented Feb 16, 2016 at 23:40

# Perl - 99 bytes

use bigint;%_=$_+=$_//1;$%+=($s=$_{$1}//=pos)<pos&&print"$-$s $-[0] "while/(?=(.{$%}))/g;$-++;do$0


Trading bytes for efficiency. n = 9 finishes in about 25s, around 15x slower than the version below.

### Perl - 120 bytes

use bigint;for$i(0..2e4){$_==($s=$_{$_[$_]}//=$_)or($%+=print"$i$s $_ "),last for 0..(@_=/(?=(.{$%}))/g);%_=$_+=$_//=1}


The regex /(?=(.{$%}))/g returns all substrings of the current value of length $%. The list is iterated, and if a value is seen twice, it is reported.

Output

0 0 1
16 1 2
24 2 3
41 8 9
73 10 18
130 14 17
371 8 52
875 68 101
2137 12 240
2900 270 355
7090 803 1123
12840 1672 3185


Output for n = 10 at about 9s, for n = 11 at 30s.

• If you use -E you can change to say"..." without the linebreak Commented Feb 16, 2016 at 17:14
• and -Mbigint  is 2 bytes shorter than use bigint; Commented Feb 16, 2016 at 17:15
• Cant you change for$i(0..2e4) to while(++$i) if you have no intentions on exiting anyway? Commented Feb 16, 2016 at 17:22
• 0..2e4 is necessary, or the output is off by one. for(;;$i++) misses the first zero. Commented Feb 16, 2016 at 17:41 # PowerShell, 168158139 135 bytes slow param($l)for(--$p;!"$j"){if(!$d){$m=@{};$i=-1$n='1'*!$l+[bigint]::Pow(2,++$p)}$d=''+$n[++$i..($i+$l-1)]$j=$m.$d;$m.$d=$i}"$p [$j$i]"


Try it online!

Less golfed:

param($l) for(--$p;!"$j"){ if(!$d){
$m=@{}$i=-1
$n='1'*!$l+[bigint]::Pow(2,++$p) # if($l -eq 0){'11'}else{'[bigint]'}
}
$d=''+$n[++$i..($i+$l-1)]$j=$m.$d
$m.$d=$i } "$p [$j$i]"


output from my notebook:

Elapsed          N     output
-------          ----- ------------------------------
00:00:00.0659394 0 =>  0 [0 1]
00:00:00.0227806 1 =>  16 [1 2]
00:00:00.1038194 2 =>  24 [2 3]
00:00:00.3169680 3 =>  41 [8 9]
00:00:01.0266805 4 =>  73 [10 18]
00:00:03.3426611 5 =>  130 [14 17]
00:00:34.3156609 6 =>  371 [8 52]
00:04:23.3928567 7 =>  875 [68 101]


# PowerShell, 187 194 bytes

Add some bytes to remove redundant iterations. Thanks @CJ Dennis

param($l)for($p=0;!($a=0..($l-1)-ge0|%{[bigint]::Pow(2,$p)-replace"^.{$_}",('-'*$_)}|sls('\d'*$l+'\b'*!$l)-a|% m*|group|? c* -ge 2|%{$i,$j=($_|% Gr*|% I*)[0,1]
,"$p [$i $j]"*($i-ne$j)})){++$p}$a  Try it online! Less golfed and slightly faster code: param($l)

$regexp = '\d'*$l+'\b'*!$l # digits or boundary$range = 0..($l-1) -ge 0$power = 0

do{
$n = [bigint]::Pow(2,$power)

$s =$range|%{$n-replace"^.{$_}",('-'*$_)}$m = $s|Select-string$regexp -AllMatches|% Matches

# $s contains strings in which a regexp captures all substrings of$l digits
# $m contains the captured matches # example with$l=3 and $p=43: # #$s               matches after $regexp # ============= ===================== # 2199023255552 -> 219 902 325 555 # -199023255552 -> 199 023 255 552 # --99023255552 -> 990 232 555$a = $m|Group|? Count -ge 2|%{$i,$j =$_|% Group|% Index|Select -First 2
if($i -ne$j){
"$power [$i $j]" } } ++$power
}
until($a) write-output$a


Try it online!

The output on my notebook:

Elapsed          N     output
-------          ----- --------------------
00:00:00.1183433 0 =>  0 [0 1]
00:00:00.0135382 1 =>  16 [1 2]
00:00:00.0135382 1 =>  16 [0 4]
00:00:00.0224871 2 =>  24 [0 6]
00:00:00.0224871 2 =>  24 [2 3]
00:00:00.0353316 3 =>  41 [9 8]
00:00:00.0649162 4 =>  73 [10 18]
00:00:00.1572769 5 =>  130 [17 14]
00:00:00.7403980 6 =>  371 [8 52]
00:00:02.6019309 7 =>  875 [101 68]
00:00:15.8726659 8 =>  2137 [240 12]
00:00:30.0988879 9 =>  2900 [270 355]
00:03:20.7172180 10 => 7090 [803 1123]

• It looks like your code doesn't get to n=9 in a minute. Commented Mar 24, 2021 at 2:07
• yes, it is. it need to take out of the loop: the [bigint], the regexp. it need to calculate the output string if $i -ne$j only. But This is code-golf, so lowest number of bytes wins! :) Commented Mar 24, 2021 at 3:52

# JavaScript (ES6), 111 bytes

n=>(C=i=>(I=S.indexOf(S.slice(i,i+n)))==i?S[i+n]?C(i+1):-1:i,P=p=>(z=C(0,S=(2n**p+'')))<0?P(++p):p,[P(0n),I,z])


It calculates the first 9 fairly quickly, but then reaches the maximum call stack size for n=10;

[0n, 0, 1]
[16n, 0, 4]
[24n, 0, 6]
[41n, 8, 9]
[73n, 10, 18]
[130n, 14, 17]
[371n, 8, 52]
[875n, 68, 101]
[2137n, 12, 240]
[2900n, 270, 355]


Here's how it works:

n=>(                                // take n as input
C=i=>                             // C finds recurring match in string S
(I=S.indexOf(S.slice(i,i+n)))   // calculate the first index of a substring
==i                           // the index of the substring being tested
?                               // if those are equal, no match
S[i+n]                        // if we're not at end of string,
?C(i+1)                       // continue recursing
:-1                           // otherwise, return -1 (no match)
:i,                             // we have a match, return i
P=p=>                             // loops over powers of 2 and check matches
(z=C(0,S=(2n**p+'')))<0         // check 2^p for match
?P(++p),                        // if no match, continue recursing
:p                              // if we find a match, return the power
[P(0n),I,z]                       // return power, first and last index
)