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
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,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
Perl 6
Meh. Not the fastest, but not horrible.
<lang perl6>use Lingua::EN::Numbers;
my $time = now;
- Brute force-ish. Ok for low powers, quickly runs out of steam
my @p2 = lazy (^Inf).hyper(:8degree).map: -> \k { floor exp(k, 2)/10**(Int(k/3.322)-3) };
multi p ($prefix, Int $nth) {
my $index = 0;
my $count = 0;
@p2.map: {
++$count if $_.starts-with($prefix);
last if $count == $nth;
++$index;
}
$index
}
- Finesse. Takes advantage of repeating patterns to avoid heavy calculations
my @i = (90,289,196,289,196),(485),(289,196),(289,196,485),(485,196,289,196,289,196); my @a = flat ('02231112223112223111223'.comb.map( { @i[$_] } ).join( " @i[4] ")).words; my @b = flat ('1112223112223111222311222311222311122231122231112223112223112223'
.comb.map( { @i[$_] } ).join( " @i[4] ")).words;
my @po2 = lazy flat @a, @b xx *;
multi p ($pre where *.chars == 3, Int $nth) { sum @po2[^$nth] }
- The task
for <12 1 12 2 123 45 123 456 123 12345 123 678910> -> $prefix, $nth {
printf "%9s power of two (2**n) that starts with %5s is at n = %s\n",
ordinal-digit($nth), "'$prefix'", comma p($prefix, $nth)
}
say "Run time seconds: ", (now - $time).round(.001);</lang>
- Output:
1st power of two (2**n) that starts with '12' is at n = 7
2nd power of two (2**n) that starts with '12' is at n = 80
45th power of two (2**n) that starts with '123' is at n = 12,710
456th power of two (2**n) that starts with '123' is at n = 129,602
12345th power of two (2**n) that starts with '123' is at n = 3,510,481
678910th power of two (2**n) that starts with '123' is at n = 193,052,248
Run time seconds: 3.363
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.