First power of 2 that has leading decimal digits of 12

From Rosetta Code
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.)


27   =   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,
280   =   1208925819614629174706176.


Define     p(L,n)     to be the nth-smallest value of   j   such that the base ten representation of   2j   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.



Factor[edit]

A translation of the first Pascal example:

Translation of: Pascal
Works with: Factor version 0.99 2019-10-06
USING: formatting fry generalizations kernel literals math
math.functions math.parser sequences tools.time ;
 
CONSTANT: ld10 $[ 2 log 10 log / ]
 
: p ( L n -- m )
swap [ 0 0 ]
[ '[ over _ >= ] ]
[ [ log10 >integer 10^ ] keep ] tri*
'[
1 + dup ld10 * dup >integer - 10 log * e^ _ * truncate
_ number= [ [ 1 + ] dip ] when
] until nip ;
 
[
12 1
12 2
123 45
123 12345
123 678910
[ 2dup p "%d %d p = %d\n" printf ] 2 5 mnapply
] time
Output:
12 1 p = 7
12 2 p = 80
123 45 p = 12710
123 12345 p = 3510491
123 678910 p = 193060223
Running time: 44.208249282 seconds

Go[edit]

Translation of: Pascal
package main
 
import (
"fmt"
"math"
"time"
)
 
const 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))
}
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

or, translating the alternative Pascal version as well, for good measure:

package main
 
import (
"fmt"
"strconv"
"time"
)
 
func p(L, n uint64) uint64 {
Ls := strconv.FormatUint(L, 10)
digits := uint64(1)
for d := 1; d <= 18-len(Ls); d++ {
digits *= 10
}
const ten18 uint64 = 1e18
var count, i, probe uint64 = 0, 0, 1
for {
probe += probe
i++
if probe >= ten18 {
for {
if probe >= ten18 {
probe /= 10
}
if probe/digits == L {
count++
if count >= n {
count--
break
}
}
probe += probe
i++
}
}
ps := strconv.FormatUint(probe, 10)
le := len(Ls)
if le > len(ps) {
le = len(ps)
}
if ps[0:le] == Ls {
count++
if count >= n {
break
}
}
}
return i
}
 
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 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))
}
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 1.422321658s

Julia[edit]

function p(L, n)
@assert(L > 0 && n > 0)
places, logof2, nfound = trunc(log(10, L)), log(10, 2), 0
for i in 1:typemax(Int)
if L == trunc(10^(((i * logof2) % 1) + places)) && (nfound += 1) == n
return i
end
end
end
 
for (L, n) in [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]
println("With L = $L and n = $n, p(L, n) = ", p(L, n))
end
 
Output:
With L = 12 and n = 1, p(L, n) = 7
With L = 12 and n = 2, p(L, n) = 80
With L = 123 and n = 45, p(L, n) = 12710
With L = 123 and n = 12345, p(L, n) = 3510491
With L = 123 and n = 678910, p(L, n) = 193060223

Faster version[edit]

Translation of: Go
using Formatting, BenchmarkTools
 
function p(L, n)
@assert(L > 0 && n > 0)
Ls, ten18, nfound, i, probe = string(L), 10^18, 0, 0, 1
maxdigits = 10^(18 - ndigits(L))
while true
probe += probe
i += 1
if probe >= ten18
while true
(probe >= ten18) && (probe ÷= 10)
if probe ÷ maxdigits == L
if (nfound += 1) >= n
nfound -= 1
break
end
end
probe += probe
i += 1
end
end
ps = string(probe)
len = min(length(Ls), length(ps))
if ps[1:len] == Ls && (nfound += 1) >= n
break
end
end
return i
end
 
function testpLn(verbose)
for (L, n) in [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]
i = p(L, n)
verbose && println("With L = $L and n = $n, p(L, n) = ", format(i, commas=true))
end
end
 
testpLn(true)
@btime testpLn(false)
 
Output:
With L = 12 and n = 1, p(L, n) = 7
With L = 12 and n = 2, p(L, n) = 80
With L = 123 and n = 45, p(L, n) = 12,710
With L = 123 and n = 12345, p(L, n) = 3,510,491
With L = 123 and n = 678910, p(L, n) = 193,060,223
  1.462 s (752 allocations: 32.19 KiB)

Pascal[edit]

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.
0<= base ** frac(x) < base thats 1 digit before the comma
Only the first digits are needed.So I think, the accuracy is sufficient, because the results are the same :-)

program Power2FirstDigits;
 
uses
sysutils,strUtils;
const
ld10= ln(2)/ln(10);// thats 1/log2(10)
 
function FindExp(CntLmt,Number:NativeUint):NativeUint;
var
i,cnt,DgtShift: NativeUInt;
begin
//calc how many Digits needed
i := Number;
DgtShift:= 1;
while i >= 10 do
Begin
DgtShift*= 10;
i := i div 10;
end;
 
cnt := 0;
i := 0;
repeat
inc(i);
// x= i*ld10 -> 2^I = 10^x
// 10^frac(x) -> [0..10[ = exp(ln(10)*frac(i*lD10))
IF trunc(DgtShift*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.
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[edit]


Now only using the fractional part for maximum precision in Uint64
ignoring overflow so frac64 is [0..2**64-1] represent [0..1[
changed trunc(DgtShift*exp(ln(10)*frac(i*lD10))) = Number
No trunc Number/Digits <= .. < (Number+1)/Digits => no trunc
Logarithm (Ln(Number/Digits)/ln(10) <= frac(i*lD10) < ln((Number+1)/Digits)/ln(10) => no exp

program Power2Digits;
uses
sysutils,strUtils;
const
L_float64 = sqr(sqr(65536.0));//2**64
Log10_2_64 = TRUNC(L_float64*ln(2)/ln(10));
 
function FindExp(CntLmt,Number:NativeUint):NativeUint;
var
Log10Num : extended;
LmtUpper,LmtLower : UInt64;
Frac64 : UInt64;
i,dgts,cnt: NativeUInt;
begin
i := Number;
dgts := 1;
while i >= 10 do
Begin
dgts *= 10;
i := i div 10;
end;
//trunc is Int64 :-( so '316' was a limit
Log10Num :=ln((Number+1)/dgts)/ln(10);
IF Log10Num >= 0.5 then
Begin
IF (Number+1)/dgts < 10 then
Begin
LmtUpper := Trunc(Log10Num*(L_float64*0.5))*2;
LmtUpper += Trunc(Log10Num*2);
end
else
LmtUpper := 0;
Log10Num :=ln(Number/dgts)/ln(10);
LmtLower := Trunc(Log10Num*(L_float64*0.5))*2;
LmtLower += Trunc(Log10Num*2);
end
Else
Begin
LmtUpper := Trunc(Log10Num*L_float64);
LmtLower := Trunc(ln(Number/dgts)/ln(10)*L_float64);
end;
 
cnt := 0;
i := 0;
Frac64 := 0;
IF LmtUpper <> 0 then
Begin
repeat
inc(i);
inc(Frac64,Log10_2_64);
IF (Frac64>= LmtLower) AND (Frac64< LmtUpper) then
Begin
inc(cnt);
IF cnt>= CntLmt then
BREAK;
end;
until false
end
Else
//searching for '999..'
Begin
repeat
inc(i);
inc(Frac64,Log10_2_64);
IF (Frac64>= LmtLower) then
Begin
inc(cnt);
IF cnt>= CntLmt then
BREAK;
end;
until false
end;
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,223);
FindExp(12345,123);
FindExp(678910,123);
 
FindExp(1,99);
end.
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 "223" is 22,670
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
The 1th  occurrence of 2 raised to a power whose product starts with "99" is 93

//64Bit
real	0m0,138s
//32Bit
real    0m0,389s

Perl[edit]

Translation of: Perl 6
use strict;
use warnings;
use feature 'say';
use feature 'state';
 
use POSIX qw(fmod);
use Perl6::GatherTake;
 
use constant ln2ln10 => log(2) / log(10);
 
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
 
sub ordinal_digit {
my($d) = $_[0] =~ /(.)$/;
$d eq '1' ? 'st' : $d eq '2' ? 'nd' : $d eq '3' ? 'rd' : 'th'
}
 
sub startswith12 {
my($nth) = @_;
state $i = 0;
state $n = 0;
while (1) {
next unless '1.2' eq substr(( 10 ** fmod(++$i * ln2ln10, 1) ), 0, 3);
return $i if ++$n eq $nth;
}
}
 
sub startswith123 {
my $pre = '1.23';
my ($this, $count) = (0, 0);
 
gather {
while (1) {
if ($this == 196) {
$this = 289;
$this = 485 unless $pre eq substr(( 10 ** fmod(($count+$this) * ln2ln10, 1) ), 0, 4);
} elsif ($this == 485) {
$this = 196;
$this = 485 unless $pre eq substr(( 10 ** fmod(($count+$this) * ln2ln10, 1) ), 0, 4);
} elsif ($this == 289) {
$this = 196
} elsif ($this == 90) {
$this = 289
} elsif ($this == 0) {
$this = 90;
}
take $count += $this;
}
}
}
 
my $start_123 = startswith123(); # lazy list
 
sub p {
my($prefix,$nth) = @_;
$prefix eq '12' ? startswith12($nth) : $start_123->[$nth-1];
}
 
for ([12, 1], [12, 2], [123, 45], [123, 12345], [123, 678910]) {
my($prefix,$nth) = @$_;
printf "%-15s %9s power of two (2^n) that starts with %5s is at n = %s\n", "p($prefix, $nth):",
comma($nth) . ordinal_digit($nth), "'$prefix'", comma p($prefix, $nth);
}
Output:
p(12, 1):             1st power of two (2^n) that starts with  '12' is at n = 7
p(12, 2):             2nd power of two (2^n) that starts with  '12' is at n = 80
p(123, 45):          45th power of two (2^n) that starts with '123' is at n = 12,710
p(123, 12345):   12,345th power of two (2^n) that starts with '123' is at n = 3,510,491
p(123, 678910): 678,910th power of two (2^n) that starts with '123' is at n = 193,060,223

Perl 6[edit]

Works with: Rakudo version 2019.11

Uses logs similar to Go and Pascal entries. Takes advantage of patterns in the powers to cut out a bunch of calculations.

use Lingua::EN::Numbers;
 
constant $ln2ln10 = log(2) / log(10);
 
my @startswith12 = ^.grep: { ( 10 ** ($_ * $ln2ln10 % 1) ).substr(0,3) eq '1.2' };
 
my @startswith123 = lazy gather loop {
state $pre = '1.23';
state $count = 0;
state $this = 0;
given $this {
when 196 {
$this = 289;
my \n = $count + $this;
$this = 485 unless ( 10 ** (n * $ln2ln10 % 1) ).substr(0,4) eq $pre;
}
when 485 {
$this = 196;
my \n = $count + $this;
$this = 485 unless ( 10 ** (n * $ln2ln10 % 1) ).substr(0,4) eq $pre;
}
when 289 { $this = 196 }
when 90 { $this = 289 }
when 0 { $this = 90 }
}
take $count += $this;
}
 
multi p ($prefix where *.chars == 2, $nth) { @startswith12[$nth-1] }
multi p ($prefix where *.chars == 3, $nth) { @startswith123[$nth-1] }
 
# The Task
for < 12 1 12 2 123 45 123 12345 123 678910 > -> $prefix, $nth {
printf "%-15s %9s power of two (2^n) that starts with %5s is at n = %s\n", "p($prefix, $nth):",
comma($nth) ~ ordinal-digit($nth).substr(*-2), "'$prefix'", comma p($prefix, $nth);
}
Output:
p(12, 1):             1st power of two (2^n) that starts with  '12' is at n = 7
p(12, 2):             2nd power of two (2^n) that starts with  '12' is at n = 80
p(123, 45):          45th power of two (2^n) that starts with '123' is at n = 12,710
p(123, 12345):   12,345th power of two (2^n) that starts with '123' is at n = 3,510,491
p(123, 678910): 678,910th power of two (2^n) that starts with '123' is at n = 193,060,223

Phix[edit]

function p(integer L, n)
atom logof2 = log10(2)
integer places = trunc(log10(L)),
nfound = 0, i = 1
while true do
atom a = i * logof2,
b = trunc(power(10,a-trunc(a)+places))
if L == b then
nfound += 1
if nfound == n then exit end if
end if
i += 1
end while
return i
end function
 
constant tests = {{12, 1}, {12, 2}, {123, 45}, {123, 12345}, {123, 678910}}
include ordinal.e
include mpfr.e
mpz z = mpz_init()
for i=1 to length(tests) do
integer {L,n} = tests[i], pln = p(L,n)
mpz_ui_pow_ui(z,2,pln)
integer digits = mpz_sizeinbase(z,10)
string st = iff(digits>2e6?sprintf("%,d digits",digits):
shorten(mpz_get_str(z),"digits",5))
printf(1,"The %d%s power of 2 that starts with %d is %d [i.e. %s]\n",{n,ord(n),L,pln,st})
end for
Output:
The 1st power of 2 that starts with 12 is 7 [i.e. 128]
The 2nd power of 2 that starts with 12 is 80 [i.e. 1208925819614629174706176]
The 45th power of 2 that starts with 123 is 12710 [i.e. 12338...09024 (3,827 digits)]
The 12345th power of 2 that starts with 123 is 3510491 [i.e. 12317...80448 (1,056,764 digits)]
The 678910th power of 2 that starts with 123 is 193060223 [i.e. 58,116,919 digits]

Python[edit]

Using logs, as seen first in the Pascal example.

from math import log, modf, floor
 
def p(l, n, pwr=2):
l = int(abs(l))
digitcount = floor(log(l, 10))
log10pwr = log(pwr, 10)
raised, found = -1, 0
while found < n:
raised += 1
firstdigits = floor(10**(modf(log10pwr * raised)[0] + digitcount))
if firstdigits == l:
found += 1
return raised
 
 
if __name__ == '__main__':
for l, n in [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]:
print(f"p({l}, {n}) =", p(l, n))
Output:
p(12, 1) = 7
p(12, 2) = 80
p(123, 45) = 12710
p(123, 12345) = 3510491
p(123, 678910) = 193060223

REXX[edit]

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

zkl[edit]

Translation of: Pascal

Lots of float are slow so I've restricted the tests.

// float*int --> float and int*float --> int
fcn p(L,nth){ // 2^j = <L><digits>
var [const] ln10=(10.0).log(), ld10=(2.0).log() / ln10;
digits := (10).pow(L.numDigits - 1);
foreach i in ([1..]){
z:=ld10*i;
if(L == ( ln10 * (z - z.toInt()) ).exp()*digits and (nth-=1) <= 0)
return(i);
}
}
Library: GMP
GNU Multiple Precision Arithmetic Library

GMP is just used to give some context on the size of the numbers we are dealing with.

var [const] BI=Import("zklBigNum");  // libGMP
tests:=T( T(12,1),T(12,2), T(123,45),T(123,12345), );
foreach L,nth in (tests){
n:=p(L,nth);
println("2^%-10,d is occurance %,d of 2^n == '%d<abc>' (%,d digits)"
.fmt(n,nth,L,BI(2).pow(n).len()));
}
Output:
2^7          is occurance 1 of 2^n == '12<abc>' (3 digits)
2^80         is occurance 2 of 2^n == '12<abc>' (25 digits)
2^12,710     is occurance 45 of 2^n == '123<abc>' (3,827 digits)
2^3,510,491  is occurance 12,345 of 2^n == '123<abc>' (1,056,764 digits)