First power of 2 that has leading decimal digits of 12

(This task is taken from a Project Euler problem.)

(All numbers herein are expressed in base ten.)

2⁷ = 128 and 7 is the first power of 2 whose leading decimal digits are 12.

The next power of 2 whose leading decimal digits are 12 is 80,
2⁸⁰ = 1208925819614629174706176.

Define p(L,n) to be the n^th-smallest value of j such that the base ten representation of 2^j begins with the digits of L .

    So   p(12, 1) =  7    and
         p(12, 2) = 80

You are also given that:

         p(123, 45)   =   12710

Task

find:

p(12, 1)
p(12, 2)
p(123, 45)
p(123, 12345)
p(123, 678910)

display the results here, on this page.

Go

Library: GMP(Go wrapper)

A (more or less) brute force approach suffices for the first 3 parts of this task but a much quicker method is needed for the other two parts.

Based on some prior analysis I did, the first three powers of two to begin with "123" are: 2^90, 2^379 and 2^575. Notice that the respective difference in powers is 90, 289 and 196.

For higher powers, after a 196 difference, I found that the next difference in powers was either 289 or 485 (= 289 + 196), that 289 was always followed by a difference of 196 and that 485 was followed by either 196 or 485 again.

However, the numbers are so large here that (even using GMP) p(123, 12345) is still taking about 4.5 minutes to compute on my Core i7 and, judging by the REXX solution, p(123, 678910) would take well in excess of 4 hours.

The REXX solution (on a 3.2GHz processor) took 275 seconds. 2^193,060,223 has over 158 million digits. -- Gerard Schildberger (talk) 19:16, 15 January 2020 (UTC) (this msg to be removed later?)

I have therefore just completed the first 4 parts for now. <lang go>package main

import (

   "fmt"
   big "github.com/ncw/gmp"
   "strconv"
   "strings"

)

func p123(n int) uint {

   power, shift := uint(0), uint(90)
   one := big.NewInt(1)
   temp := new(big.Int)
   for count := 0; count < n; count++ {
       power += shift
       switch shift {
       case 90:
           shift = 289
       case 289:
           shift = 196
       case 196:
           shift = 289
           temp.Set(one)
           temp.Lsh(temp, power+289)
           if !strings.HasPrefix(temp.String(), "123") {
               shift = 485
           }
       case 485:
           shift = 196
           temp.Set(one)
           temp.Lsh(temp, power+196)
           if !strings.HasPrefix(temp.String(), "123") {
               shift = 485
           }
       }
   }
   return power

}

func p(L, n int) uint {

   prefix := strconv.Itoa(L)
   if prefix == "123" {
       return p123(n)
   }
   count := 0
   power, shift := uint(1), uint(1)
   i := big.NewInt(1)
   for {
       i := i.Lsh(i, shift)
       if strings.HasPrefix(i.String(), prefix) {
           count++
           if count == n {
               break
           }
           shift = 4 // next number is going to be more than 8 times as big
       } else {
           shift = 1
       }
       power += shift
   }
   return power

}

func commatize(n uint) string {

   s := fmt.Sprintf("%d", n)
   le := len(s)
   for i := le - 3; i >= 1; i -= 3 {
       s = s[0:i] + "," + s[i:]
   }
   return s

}

func main() {

   params := [][2]int{{12, 1}, {12, 2}, {123, 45}, {123, 12345},} // {123, 678910} }
   for _, param := range params {
       fmt.Printf("p(%d, %d) = %s\n", param[0], param[1], commatize(p(param[0], param[1])))
   }

}</lang>

Output:

p(12, 1) = 7
p(12, 2) = 80
p(123, 45) = 12,710
p(123, 12345) = 3,510,491

Pascal

First convert 2**i -> 10**x => x= ln(2)/ln(10) *i
The integer part of x is the position of the comma.Only the fraction of x leads to the digits. Only the first digits are needed.So I think, the accuracy is sufficient, because the results are the same :-) <lang pascal>program Power2FirstDigits;

uses

 sysutils,strUtils;

const

 ld10= ln(2)/ln(10);

function FindExp(CntLmt,Number:NativeUint):NativeUint; var

 i,dgts,cnt: NativeUInt;

begin

 i := Number;
 dgts := 1;
 while i >= 10 do
 Begin
   dgts *= 10;
   i := i div 10;
 end;

 cnt := 0;
 i := 0;
 repeat
   inc(i);
   IF trunc(dgts*exp(ln(10)*frac(i*lD10))) = Number then
   Begin
     inc(cnt);
     IF cnt>= CntLmt then
       BREAK;
   end;
 until false;
 write('The  ',Numb2USA(IntToStr(cnt)),'th  occurrence of 2 raised to a power');
 write(' whose product starts with "',Numb2USA(IntToStr(number)));
 writeln('" is ',Numb2USA(IntToStr(i)));
 FindExp := i;

end;

Begin

 FindExp(1,12);
 FindExp(2,12);

 FindExp(45,123);
 FindExp(12345,123);
 FindExp(678910,123);

end.

 cnt := 0;
 CntLmt := 678910-10;
 for i := 1 to 193060223 do
 Begin
   x:= 100*exp(ln(10)*frac(i*lD10));
   IF trunc(x) = 123 then
   Begin
     inc(cnt);
     IF cnt>= CntLmt then
       writeln(cnt:8,i:10,trunc(x):5)
   end;
 end;

end.</lang>

Output:

The  1th  occurrence of 2 raised to a power whose product starts with "12" is 7
The  2th  occurrence of 2 raised to a power whose product starts with "12" is 80
The  45th  occurrence of 2 raised to a power whose product starts with "123" is 12,710
The  12,345th  occurrence of 2 raised to a power whose product starts with "123" is 3,510,491
The  678,910th  occurrence of 2 raised to a power whose product starts with "123" is 193,060,223
//64Bit real    0m43,031s //32Bit real	0m13,363s

REXX

<lang rexx>/*REXX program computes powers of two whose leading decimal digits are "12" (in base 10)*/ parse arg L n b . /*obtain optional arguments from the CL*/ if L== | L=="," then L= 12 /*Not specified? Then use the default.*/ if n== | n=="," then n= 1 /* " " " " " " */ if b== | b=="," then b= 2 /* " " " " " " */ LL= length(L) /*obtain the length of L for compares*/ fd= left(L, 1) /*obtain the first dec. digit of L.*/ fr= substr(L, 2) /* " " rest of dec. digits " " */ numeric digits max(20, LL+2) /*use an appropriate value of dec. digs*/ rest= LL - 1 /*the length of the rest of the digits.*/

= 0 /*the number of occurrences of a result*/

x= 1 /*start with a product of unity (B**0).*/

    do j=1  until #==n;        x= x * b         /*raise  B  to a whole bunch of powers.*/
    parse var x _ 2                             /*obtain the first decimal digit of  X.*/
    if _ \== fd  then iterate                   /*check only the 1st digit at this time*/
    if LL>1  then do                            /*check the rest of the digits, maybe. */
                  $= format(x, , , , 0)         /*express  X  in exponential format.   */
                  parse var $ '.' +1 f +(rest)  /*obtain the rest of the digits.       */
                  if f \== fr  then iterate     /*verify that  X  has the rest of digs.*/
                  end                           /* [↓] found an occurrence of an answer*/
    #= # + 1                                    /*bump the number of occurrences so far*/
    end   /*j*/

say 'The ' th(n) ' occurrence of ' b ' raised to a power whose product starts with' ,

                                                 ' "'L"'"       ' is '        commas(j).

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: arg _; do c=length(_)-3 to 1 by -3; _= insert(',', _, c); end; return _ th: arg _; return _ || word('th st nd rd', 1 +_//10 * (_//100 % 10\==1) * (_//10 <4))</lang>

output when using the inputs of: 12 1

The  1st  occurrence of  2  raised to a power whose product starts with  "12'  is  7.

output when using the inputs of: 12 2

The  2nd  occurrence of  2  raised to a power whose product starts with  "12'  is  80.

output when using the inputs of: 123 45

The  45th  occurrence of  2  raised to a power whose product starts with  "123'  is  12,710.

output when using the inputs of: 123 12345

The  12345th  occurrence of  2  raised to a power whose product starts with  "123'  is  3,510,491.

output when using the inputs of: 123 678910

The  678910th  occurrence of  2  raised to a power whose product starts with  "123'  is  193,060,223.