5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I don't get it, should we output only the lowest power of 2, or as many as we can find in one minute? \$\endgroup\$ – Katenkyo Feb 16 '16 at 8:26
  • \$\begingroup\$ @CJDennis Should we time it ourself (and halt it) or we can just let it run? \$\endgroup\$ – Katenkyo Feb 16 '16 at 8:33
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ – primo Feb 16 '16 at 11:48
4
\$\begingroup\$

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}}}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – CJ Dennis Feb 16 '16 at 8:33
  • \$\begingroup\$ @CJDennis Actually, that's the natural expression. I didn't add these braces intentionally. \$\endgroup\$ – njpipeorgan Feb 16 '16 at 8:37
  • \$\begingroup\$ @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. \$\endgroup\$ – Katenkyo Feb 16 '16 at 9:33
  • \$\begingroup\$ @Katenkyo 2199023255552 overlaps with 2199023255552 \$\endgroup\$ – njpipeorgan Feb 16 '16 at 9:37
  • \$\begingroup\$ @njpipeorgan nevermind, just saw overlapping matches are authorized... Which totally invalidate what i was working on. \$\endgroup\$ – Katenkyo Feb 16 '16 at 9:40
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – btwlf Feb 16 '16 at 23:40
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If you use -E you can change to say"..." without the linebreak \$\endgroup\$ – andlrc Feb 16 '16 at 17:14
  • \$\begingroup\$ and -Mbigint is 2 bytes shorter than use bigint; \$\endgroup\$ – andlrc Feb 16 '16 at 17:15
  • \$\begingroup\$ Cant you change for$i(0..2e4) to while(++$i) if you have no intentions on exiting anyway? \$\endgroup\$ – andlrc Feb 16 '16 at 17:22
  • \$\begingroup\$ 0..2e4 is necessary, or the output is off by one. for(;;$i++) misses the first zero. \$\endgroup\$ – primo Feb 16 '16 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.