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.)
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
A translation of the first Pascal example:
<lang factor>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</lang>
- 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
<lang go>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))
}</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
or, translating the alternative Pascal version as well, for good measure: <lang go>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))
}</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 1.422321658s
Julia
<lang julia>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
</lang>
- 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
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.
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 :-)
<lang pascal>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.</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
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
<lang pascal>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.</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 "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 6
Uses logs similar to Go and Pascal entries. Takes advantage of patterns in the powers to cut out a bunch of calculations.
<lang perl6>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);
}</lang>
- 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
<lang Phix>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</lang>
- 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
Using logs, as seen first in the Pascal example.
<lang python>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))</lang>
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
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.
zkl
Lots of float are slow so I've restricted the tests. <lang zkl>// 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);
}
}</lang>
GNU Multiple Precision Arithmetic Library
GMP is just used to give some context on the size of the numbers we are dealing with. <lang zkl>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()));
}</lang>
- 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)