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

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

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.