First power of 2 that has leading decimal digits of 12: Difference between revisions
No edit summary |
|||
Line 271: | Line 271: | ||
Took 1.422321658s |
Took 1.422321658s |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
{{trans|Python}} |
|||
<lang haskell>import Control.Monad (guard) |
|||
import Text.Printf (printf) |
|||
p :: Integer -> Int -> Integer |
|||
p l n = calc !! pred n |
|||
where |
|||
digitCount = floor $ logBase 10 (fromIntegral l :: Float) |
|||
log10pwr = logBase 10 2 |
|||
calc = do |
|||
raised <- [-1 ..] |
|||
let firstDigits = floor $ 10 ** (snd (properFraction $ log10pwr * realToFrac raised) + realToFrac digitCount) |
|||
guard (firstDigits == l) |
|||
[raised] |
|||
main :: IO () |
|||
main = mapM_ (\(l, n) -> printf "p(%d, %d) = %d\n" l n (p l n)) |
|||
[(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]</lang> |
|||
{{out}} |
|||
<pre>p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Modeled on the python version. Depending on the part of speech defined, the variable names x, y, u, v, m, and n can have special meaning within explicit code. They are defined by the arguments. In the fonts I usually use, lower case "l" is troublesome as well. |
Modeled on the python version. Depending on the part of speech defined, the variable names x, y, u, v, m, and n can have special meaning within explicit code. They are defined by the arguments. In the fonts I usually use, lower case "l" is troublesome as well. |
Revision as of 18:57, 21 May 2020
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
(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.
ALGOL 68
As wih the Go second sample, computes approximate integer values for the powers of 2.
Requires LONG INT to be at least 64 bits (as in Algol 68G).
<lang algol68># find values of p( L, n ) where p( L, n ) is the smallest j such that #
- the decimal representation of 2^j starts with n #
BEGIN
# returns a string representation of n with commas # PROC commatise = ( LONG INT n )STRING: BEGIN STRING result := ""; STRING unformatted = whole( n, 0 ); INT ch count := 0; FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO IF ch count <= 2 THEN ch count +:= 1 ELSE ch count := 1; "," +=: result FI; unformatted[ c ] +=: result OD; result END # commatise # ; # returns p( prefix, occurance ) # PROC p = ( INT prefix, INT occurance )LONG INT: BEGIN LONG INT quarter long max int = long max int OVER 4; LONG INT p2 := 1; INT count := 0; INT power := 0; WHILE count < occurance DO power +:= 1; p2 +:= p2; LONG INT pre := p2; WHILE pre > prefix DO pre OVERAB 10 OD; IF pre = prefix THEN count +:= 1 FI; IF p2 > quarter long max int THEN p2 OVERAB 10 000 FI OD; power END # p # ; # prints p( prefix, occurance ) # PROC print p = ( INT prefix, INT occurance )VOID: print( ( "p(", whole( prefix, 0 ), ", ", whole( occurance, 0 ), ") = ", commatise( p( prefix, occurance ) ), newline ) ); # task test cases # print p( 12, 1 ); print p( 12, 2 ); print p( 123, 45 ); print p( 123, 12345 ); print p( 123, 678910 )
END</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
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
Haskell
<lang haskell>import Control.Monad (guard) import Text.Printf (printf)
p :: Integer -> Int -> Integer p l n = calc !! pred n
where digitCount = floor $ logBase 10 (fromIntegral l :: Float) log10pwr = logBase 10 2 calc = do raised <- [-1 ..] let firstDigits = floor $ 10 ** (snd (properFraction $ log10pwr * realToFrac raised) + realToFrac digitCount) guard (firstDigits == l) [raised]
main :: IO () main = mapM_ (\(l, n) -> printf "p(%d, %d) = %d\n" l n (p l n))
[(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]</lang>
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
J
Modeled on the python version. Depending on the part of speech defined, the variable names x, y, u, v, m, and n can have special meaning within explicit code. They are defined by the arguments. In the fonts I usually use, lower case "l" is troublesome as well. <lang J> p=: adverb define
el =. x en =. y pwr =. m el =. <. | el digitcount =. <. 10 ^. el log10pwr =. 10 ^. pwr 'raised found' =. _1 0 while. found < en do. raised =. >: raised firstdigits =. (<.!.0) 10^digitcount + 1 | log10pwr * raised found =. found + firstdigits = el end. raised
) </lang>
12 12 123 123 123 (,. ,. (2 p)&>) 1 2 45 12345 678910 12 1 7 12 2 80 123 45 12710 123 12345 3510491 123 678910 193060223
Java
<lang java> public class FirstPowerOfTwo {
public static void main(String[] args) { runTest(12, 1); runTest(12, 2); runTest(123, 45); runTest(123, 12345); runTest(123, 678910); } private static void runTest(int l, int n) { System.out.printf("p(%d, %d) = %,d%n", l, n, p(l, n)); } public static int p(int l, int n) { int test = 0; double log = Math.log(2) / Math.log(10); int factor = 1; int loop = l; while ( loop > 10 ) { factor *= 10; loop /= 10; } while ( n > 0) { test++; int val = (int) (factor * Math.pow(10, test * log % 1)); if ( val == l ) { n--; } } return test; }
} </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
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
Faster version
<lang julia>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)
</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) = 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)
Kotlin
<lang scala>import kotlin.math.ln import kotlin.math.pow
fun main() {
runTest(12, 1) runTest(12, 2) runTest(123, 45) runTest(123, 12345) runTest(123, 678910)
}
private fun runTest(l: Int, n: Int) { // System.out.printf("p(%d, %d) = %,d%n", l, n, p(l, n))
println("p($l, $n) = %,d".format(p(l, n)))
}
fun p(l: Int, n: Int): Int {
var m = n var test = 0 val log = ln(2.0) / ln(10.0) var factor = 1 var loop = l while (loop > 10) { factor *= 10 loop /= 10 } while (m > 0) { test++ val value = (factor * 10.0.pow(test * log % 1)).toInt() if (value == l) { m-- } } return test
}</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
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
<lang perl>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);
}</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
Raku
(formerly 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
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.
Sidef
<lang ruby>func farey_approximations(r, callback) {
var (a1 = r.int, b1 = 1) var (a2 = a1+1, b2 = 1)
loop { var a3 = a1+a2 var b3 = b1+b2
if (a3 < r*b3) { (a1, b1) = (a3, b3) } else { (a2, b2) = (a3, b3) }
callback(a3 / b3) }
}
func p(L, nth) {
define ln2 = log(2) define ln5 = log(5) define ln10 = log(10)
var t = L.len-1
func isok(n) { floor(exp(ln2*(n - floor((n*ln2)/ln10) + t) + ln5*(t - floor((n*ln2)/ln10)))) == L }
var deltas = gather { farey_approximations(ln2/ln10, {|r| take(r.de) if (r.de.len == L.len) break if (r.de.len > L.len) }) }.sort.uniq
var c = 0 var k = (1..Inf -> first(isok))
loop { return k if (++c == nth) k += (deltas.first {|d| isok(k+d) } \\ die "error: #{k}") }
}
var tests = [
[12, 1], [12, 2], [123, 45], [123, 12345], [123, 678910],
# extra [1234, 10000], [12345, 10000],
]
for a,b in (tests) {
say "p(#{a}, #{b}) = #{p(a,b)}"
}</lang>
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223 p(1234, 10000) = 28417587 p(12345, 10000) = 284166722
Swift
Slower Version
<lang swift>let ld10 = log(2.0) / log(10.0)
func p(L: Int, n: Int) -> Int {
var l = L var digits = 1
while l >= 10 { digits *= 10 l /= 10 }
var count = 0 var i = 0
while count < n { let rhs = (Double(i) * ld10).truncatingRemainder(dividingBy: 1) let e = exp(log(10.0) * rhs)
if Int(e * Double(digits)) == L { count += 1 }
i += 1 }
return i - 1
}
let cases = [
(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)
]
for (l, n) in cases {
print("p(\(l), \(n)) = \(p(L: l, n: n))")
}</lang>
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
Faster Version
<lang swift>import Foundation
func p2(L: Int, n: Int) -> Int {
let asString = String(L) var digits = 1
for _ in 1...18-asString.count { digits *= 10 }
let ten18 = Int(1e18)
var count = 0, i = 0, probe = 1
while true { probe += probe i += 1
if probe >= ten18 { while true { if probe >= ten18 { probe /= 10 }
if probe / digits == L { count += 1
if count >= n { count -= 1 break } }
probe += probe i += 1 } }
let probeString = String(probe) var len = asString.count
if asString.count > probeString.count { len = probeString.count }
if probeString.prefix(len) == asString { count += 1
if count >= n { break } } }
return i
}
let cases = [
(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)
]
for (l, n) in cases {
print("p(\(l), \(n)) = \(p2(L: l, n: n))")
}</lang>
- Output:
Same as before.
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)