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

Question

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 code-golf, so lowest number of bytes wins!

Answer 1

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

Answer 2

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}}}

Answer 3

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

Answer 4

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.

Answer 5

PowerShell, 168 158 139 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]

Answer 6

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
)