First power of 2 that has leading decimal digits of 12: Difference between revisions
m (temporarily added a (forced) TOC.) |
m (→{{header|Pascal}}: alternative only using one Uint64) |
||
Line 152: | Line 152: | ||
The 678,910th occurrence of 2 raised to a power whose product starts with "123" is 193,060,223 |
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</pre> |
//64Bit real 0m43,031s //32Bit real 0m13,363s</pre> |
||
===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 : Uint64; |
|||
i,cnt: NativeUInt; |
|||
begin |
|||
cnt := 0; |
|||
i := 0; |
|||
Probe := 1; |
|||
repeat |
|||
inc(Probe,Probe); |
|||
inc(i); |
|||
// if 2**i gets to big divide by one digit = 10 |
|||
If Probe >= 1000*1000*1000 *1000*1000*1000 then |
|||
Probe := Probe DIV 10; |
|||
//Check the first characters of the number |
|||
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> |
|||
{{out}} |
|||
<pre>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 0m22,931s |
|||
//Without IF COPY(IntToStr(Probe),1,Length(number)) = Number then |
|||
FindExp(193060223,'123') takes |
|||
real 0m0,212s</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 21:13, 15 January 2020
(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.
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
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 : Uint64; i,cnt: NativeUInt;
begin
cnt := 0; i := 0; Probe := 1; repeat inc(Probe,Probe); inc(i); // if 2**i gets to big divide by one digit = 10 If Probe >= 1000*1000*1000 *1000*1000*1000 then Probe := Probe DIV 10; //Check the first characters of the number 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 0m22,931s //Without IF COPY(IntToStr(Probe),1,Length(number)) = Number then FindExp(193060223,'123') takes real 0m0,212s
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.