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

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 2

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 3

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.