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"
)
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
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
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,dgts : Uint64; i,cnt,n: NativeUInt;
begin
dgts := 1; For i := 1 to 18-Length(Number) do dgts *=10; n := StrToInt(Number); cnt := 0; i := 0; Probe := 1; repeat inc(Probe,Probe); inc(i); If Probe >= 1000*1000*1000 *1000*1000*1000 then repeat If Probe >= 1000*1000*1000 *1000*1000*1000 then Probe := Probe DIV 10; // get rid of converting into string IF Probe DIV dgts = n then Begin inc(cnt); IF cnt>= CntLmt then Begin DEC(cnt);// because the BREAK in the next IF BREAK; end; end; inc(Probe,Probe); inc(i); until false;
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 0m0,981s
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)