9
\$\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\$
3
  • \$\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
  • 4
    \$\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
5
+200
\$\begingroup\$

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
\$\endgroup\$
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}}}
\$\endgroup\$
5
  • \$\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

\$\endgroup\$
1
  • \$\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.

\$\endgroup\$
4
  • \$\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
1
\$\begingroup\$

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]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It looks like your code doesn't get to n=9 in a minute. \$\endgroup\$ – CJ Dennis Mar 24 at 2:07
  • \$\begingroup\$ 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! :) \$\endgroup\$ – mazzy Mar 24 at 3:52
0
\$\begingroup\$

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
)
\$\endgroup\$

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.