First power of 2 that has leading decimal digits of 12

First power of 2 that has leading decimal digits of 12 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

(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

Translation of: Pascal

<lang go>package main

import (

   "fmt"
   "math"
   "time"

)

var ld10 = math.Ln2 / math.Ln10

func commatize(n uint64) 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 p(L, n uint64) uint64 {

   i := L
   digits := uint64(1)
   for i >= 10 {
       digits *= 10
       i /= 10
   }
   count := uint64(0)
   for i = 0; count < n; i++ {
       e := math.Exp(math.Ln10 * math.Mod(float64(i)*ld10, 1))
       if uint64(math.Trunc(e*float64(digits))) == L {
           count++            
       }
   }
   return i - 1

}

func main() {

   start := time.Now()
   params := [][2]uint64{{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])))
   }
   fmt.Printf("\nTook %s\n", time.Since(start))

}</lang>

Output:

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

Took 38.015225244s

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.</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

alternative

Using only the first digits of 2**i in an Uint64 suffices. <lang pascal>program Power2Digits; uses

 sysutils,strUtils;

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

 probe : Uint64;
 i,cnt: NativeUInt;

begin

 cnt := 0;
 i := 0;
 Probe := 1;
 repeat
   inc(Probe,Probe);
   inc(i);
   // if 2**i gets to big divide by one digit = 10
   If Probe >= 1000*1000*1000 *1000*1000*1000 then
     Probe := Probe DIV 10;
   //Check the first characters of the number
   IF COPY(IntToStr(Probe),1,Length(number)) = 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(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.</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

real    0m22,931s
//Without IF COPY(IntToStr(Probe),1,Length(number)) = Number then
FindExp(193060223,'123') takes
real	0m0,212s

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.*/

1. = 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.