First power of 2 that has leading decimal digits of 12: Difference between revisions
PascalABC.NET |
|||
(45 intermediate revisions by 21 users not shown) | |||
Line 35: | Line 35: | ||
::* display the results here, on this page. |
::* display the results here, on this page. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F p(=l, n, pwr = 2) |
|||
l = Int(abs(l)) |
|||
V digitcount = floor(log(l, 10)) |
|||
V log10pwr = log(pwr, 10) |
|||
V (raised, found) = (-1, 0) |
|||
L found < n |
|||
raised++ |
|||
V firstdigits = floor(10 ^ (fract(log10pwr * raised) + digitcount)) |
|||
I firstdigits == l |
|||
found++ |
|||
R raised |
|||
L(l, n) [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)] |
|||
print(‘p(’l‘, ’n‘) = ’p(l, n))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
As wih the Go second sample, computes approximate integer values for the powers of 2. |
As wih the Go second sample, computes approximate integer values for the powers of 2. |
||
<br>Requires LONG INT to be at least 64 bits (as in Algol 68G). |
<br>Requires LONG INT to be at least 64 bits (as in Algol 68G). |
||
< |
<syntaxhighlight lang="algol68"># find values of p( L, n ) where p( L, n ) is the nth-smallest j such that # |
||
# the decimal representation of 2^j starts with |
# the decimal representation of 2^j starts with the digits of L # |
||
BEGIN |
BEGIN |
||
# returns a string representation of n with commas # |
# returns a string representation of n with commas # |
||
Line 88: | Line 115: | ||
print p( 123, 12345 ); |
print p( 123, 12345 ); |
||
print p( 123, 678910 ) |
print p( 123, 678910 ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 96: | Line 123: | ||
p(123, 12345) = 3,510,491 |
p(123, 12345) = 3,510,491 |
||
p(123, 678910) = 193,060,223 |
p(123, 678910) = 193,060,223 |
||
</pre> |
|||
=={{header|BASIC256}}== |
|||
<syntaxhighlight lang="basic256">global FAC |
|||
FAC = 0.30102999566398119521373889472449302677 |
|||
print p(12, 1) |
|||
print p(12, 2) |
|||
print p(123, 45) |
|||
print p(123, 12345) |
|||
print p(123, 678910) |
|||
end |
|||
function p(L, n) |
|||
cont = 0 : j = 0 |
|||
LS = string(L) |
|||
while cont < n |
|||
j += 1 |
|||
x = FAC * j |
|||
if x < length(LS) then continue while |
|||
y = 10^(x-int(x)) |
|||
y *= 10^length(LS) |
|||
digits = string(y) |
|||
if left(digits,length(LS)) = LS then cont += 1 |
|||
end while |
|||
return j |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
=={{header|C}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="c">#include <math.h> |
|||
#include <stdio.h> |
|||
int p(int l, int n) { |
|||
int test = 0; |
|||
double logv = log(2.0) / log(10.0); |
|||
int factor = 1; |
|||
int loop = l; |
|||
while (loop > 10) { |
|||
factor *= 10; |
|||
loop /= 10; |
|||
} |
|||
while (n > 0) { |
|||
int val; |
|||
test++; |
|||
val = (int)(factor * pow(10.0, fmod(test * logv, 1))); |
|||
if (val == l) { |
|||
n--; |
|||
} |
|||
} |
|||
return test; |
|||
} |
|||
void runTest(int l, int n) { |
|||
printf("p(%d, %d) = %d\n", l, n, p(l, n)); |
|||
} |
|||
int main() { |
|||
runTest(12, 1); |
|||
runTest(12, 2); |
|||
runTest(123, 45); |
|||
runTest(123, 12345); |
|||
runTest(123, 678910); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223</pre> |
|||
=={{header|C++}}== |
|||
{{trans|Java}} |
|||
{{trans|Go}} |
|||
{{trans|Pascal}} |
|||
<syntaxhighlight lang="cpp">// a mini chrestomathy solution |
|||
#include <string> |
|||
#include <chrono> |
|||
#include <cmath> |
|||
#include <locale> |
|||
using namespace std; |
|||
using namespace chrono; |
|||
// translated from java example |
|||
unsigned int js(int l, int n) { |
|||
unsigned int res = 0, f = 1; |
|||
double lf = log(2) / log(10), ip; |
|||
for (int i = l; i > 10; i /= 10) f *= 10; |
|||
while (n > 0) |
|||
if ((int)(f * pow(10, modf(++res * lf, &ip))) == l) n--; |
|||
return res; |
|||
} |
|||
// translated from go integer example (a.k.a. go translation of pascal alternative example) |
|||
unsigned int gi(int ld, int n) { |
|||
string Ls = to_string(ld); |
|||
unsigned int res = 0, count = 0; unsigned long long f = 1; |
|||
for (int i = 1; i <= 18 - Ls.length(); i++) f *= 10; |
|||
const unsigned long long ten18 = 1e18; unsigned long long probe = 1; |
|||
do { |
|||
probe <<= 1; res++; if (probe >= ten18) { |
|||
do { |
|||
if (probe >= ten18) probe /= 10; |
|||
if (probe / f == ld) if (++count >= n) { count--; break; } |
|||
probe <<= 1; res++; |
|||
} while (1); |
|||
} |
|||
string ps = to_string(probe); |
|||
if (ps.substr(0, min(Ls.length(), ps.length())) == Ls) if (++count >= n) break; |
|||
} while (1); |
|||
return res; |
|||
} |
|||
// translated from pascal alternative example |
|||
unsigned int pa(int ld, int n) { |
|||
const double L_float64 = pow(2, 64); |
|||
const unsigned long long Log10_2_64 = (unsigned long long)(L_float64 * log(2) / log(10)); |
|||
double Log10Num; unsigned long long LmtUpper, LmtLower, Frac64; |
|||
int res = 0, dgts = 1, cnt; |
|||
for (int i = ld; i >= 10; i /= 10) dgts *= 10; |
|||
Log10Num = log((ld + 1.0) / dgts) / log(10); |
|||
// '316' was a limit |
|||
if (Log10Num >= 0.5) { |
|||
LmtUpper = (ld + 1.0) / dgts < 10.0 ? (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2) : 0; |
|||
Log10Num = log((double)ld / dgts) / log(10); |
|||
LmtLower = (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2); |
|||
} else { |
|||
LmtUpper = (unsigned long long)(Log10Num * L_float64); |
|||
LmtLower = (unsigned long long)(log((double)ld / dgts) / log(10) * L_float64); |
|||
} |
|||
cnt = 0; Frac64 = 0; if (LmtUpper != 0) { |
|||
do { |
|||
res++; Frac64 += Log10_2_64; |
|||
if ((Frac64 >= LmtLower) & (Frac64 < LmtUpper)) |
|||
if (++cnt >= n) break; |
|||
} while (1); |
|||
} else { // '999..' |
|||
do { |
|||
res++; Frac64 += Log10_2_64; |
|||
if (Frac64 >= LmtLower) if (++cnt >= n) break; |
|||
} while (1); |
|||
}; |
|||
return res; |
|||
} |
|||
int params[] = { 12, 1, 12, 2, 123, 45, 123, 12345, 123, 678910, 99, 1 }; |
|||
void doOne(string name, unsigned int (*func)(int a, int b)) { |
|||
printf("%s version:\n", name.c_str()); |
|||
auto start = steady_clock::now(); |
|||
for (int i = 0; i < size(params); i += 2) |
|||
printf("p(%3d, %6d) = %'11u\n", params[i], params[i + 1], func(params[i], params[i + 1])); |
|||
printf("Took %f seconds\n\n", duration<double>(steady_clock::now() - start).count()); |
|||
} |
|||
int main() { |
|||
setlocale(LC_ALL, ""); |
|||
doOne("java simple", js); |
|||
doOne("go integer", gi); |
|||
doOne("pascal alternative", pa); |
|||
}</syntaxhighlight> |
|||
{{out}}Exeution times from Tio.run, language: C++ (clang) or C++ (gcc), compiler flags: -O3 -std=c++17 |
|||
<pre>java simple version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 11.350696 seconds |
|||
go integer version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 1.787658 seconds |
|||
pascal alternative version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 0.299815 seconds |
|||
</pre>Execution times on a core i7-7700 @ 3.6Ghz, g++, compiler flags: -O3 -std=c++17 |
|||
<pre>java simple version: |
|||
... |
|||
Took 15.060563 seconds |
|||
go integer version: |
|||
... |
|||
Took 1.268436 seconds |
|||
pascal alternative version: |
|||
... |
|||
Took 0.082407 seconds</pre> |
|||
=={{header|C sharp|C#}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="csharp">// a mini chrestomathy solution |
|||
using System; |
|||
class Program { |
|||
// translated from java example |
|||
static long js(int l, int n) { |
|||
long res = 0, f = 1; |
|||
double lf = Math.Log10(2); |
|||
for (int i = l; i > 10; i /= 10) f *= 10; |
|||
while (n > 0) |
|||
if ((int)(f * Math.Pow(10, ++res * lf % 1)) == l) n--; |
|||
return res; |
|||
} |
|||
// translated from go integer example (a.k.a. go translation of pascal alternative example) |
|||
static long gi(int ld, int n) { |
|||
string Ls = ld.ToString(); |
|||
long res = 0, count = 0, f = 1; |
|||
for (int i = 1; i <= 18 - Ls.Length; i++) f *= 10; |
|||
const long ten18 = (long)1e18; long probe = 1; |
|||
do { |
|||
probe <<= 1; res++; if (probe >= ten18) |
|||
do { |
|||
if (probe >= ten18) probe /= 10; |
|||
if (probe / f == ld) |
|||
if (++count >= n) { count--; break; } |
|||
probe <<= 1; res++; |
|||
} while (true); |
|||
string ps = probe.ToString(); |
|||
if (ps.Substring(0, Math.Min(Ls.Length, ps.Length)) == Ls) |
|||
if (++count >= n) break; |
|||
} while (true); |
|||
return res; |
|||
} |
|||
// translated from pascal alternative example |
|||
static long pa(int ld, int n) { |
|||
double L_float64 = Math.Pow(2, 64); |
|||
ulong Log10_2_64 = (ulong)(L_float64 * Math.Log10(2)); |
|||
double Log10Num; ulong LmtUpper, LmtLower, Frac64; |
|||
long res = 0, dgts = 1, cnt; |
|||
for (int i = ld; i >= 10; i /= 10) dgts *= 10; |
|||
Log10Num = Math.Log10((ld + 1.0) / dgts); |
|||
// '316' was a limit |
|||
if (Log10Num >= 0.5) { |
|||
LmtUpper = (ld + 1.0) / dgts < 10.0 ? (ulong)(Log10Num * (L_float64 * 0.5)) * 2 + (ulong)(Log10Num * 2) : 0; |
|||
Log10Num = Math.Log10((double)ld / dgts); |
|||
LmtLower = (ulong)(Log10Num * (L_float64 * 0.5)) * 2 + (ulong)(Log10Num * 2); |
|||
} else { |
|||
LmtUpper = (ulong)(Log10Num * L_float64); |
|||
LmtLower = (ulong)(Math.Log10((double)ld / dgts) * L_float64); |
|||
} |
|||
cnt = 0; Frac64 = 0; if (LmtUpper != 0) |
|||
do { |
|||
res++; Frac64 += Log10_2_64; |
|||
if ((Frac64 >= LmtLower) & (Frac64 < LmtUpper)) |
|||
if (++cnt >= n) break; |
|||
} while (true); |
|||
else // '999..' |
|||
do { |
|||
res++; Frac64 += Log10_2_64; |
|||
if (Frac64 >= LmtLower) if (++cnt >= n) break; |
|||
} while (true); |
|||
return res; |
|||
} |
|||
static int[] values = new int[] { 12, 1, 12, 2, 123, 45, 123, 12345, 123, 678910, 99, 1 }; |
|||
static void doOne(string name, Func<int, int, long> fun) { |
|||
Console.WriteLine("{0} version:", name); |
|||
var start = DateTime.Now; |
|||
for (int i = 0; i < values.Length; i += 2) |
|||
Console.WriteLine("p({0,3}, {1,6}) = {2,11:n0}", values[i], values[i + 1], fun(values[i], values[i + 1])); |
|||
Console.WriteLine("Took {0} seconds\n", DateTime.Now - start); |
|||
} |
|||
static void Main() { |
|||
doOne("java simple", js); |
|||
doOne("go integer", gi); |
|||
doOne("pascal alternative", pa); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
Results on the core i7-7700 @ 3.6Ghz. |
|||
<pre>java simple version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 00:00:09.5992122 seconds |
|||
go integer version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 00:00:01.5335699 seconds |
|||
pascal alternative version: |
|||
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 |
|||
p( 99, 1) = 93 |
|||
Took 00:00:00.1391226 seconds</pre> |
|||
=={{header|D}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="d">import std.math; |
|||
import std.stdio; |
|||
int p(int l, int n) { |
|||
int test = 0; |
|||
double logv = log(2.0) / log(10.0); |
|||
int factor = 1; |
|||
int loop = l; |
|||
while (loop > 10) { |
|||
factor *= 10; |
|||
loop /= 10; |
|||
} |
|||
while (n > 0) { |
|||
int val; |
|||
test++; |
|||
val = cast(int)(factor * pow(10.0, fmod(test * logv, 1))); |
|||
if (val == l) { |
|||
n--; |
|||
} |
|||
} |
|||
return test; |
|||
} |
|||
void runTest(int l, int n) { |
|||
writefln("p(%d, %d) = %d", l, n, p(l, n)); |
|||
} |
|||
void main() { |
|||
runTest(12, 1); |
|||
runTest(12, 2); |
|||
runTest(123, 45); |
|||
runTest(123, 12345); |
|||
runTest(123, 678910); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223</pre> |
|||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/First_power_of_2_that_has_leading_decimal_digits_of_12#Pascal Pascal]. |
|||
=={{header|EasyLang}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang=text> |
|||
func p l n . |
|||
log = log10 2 |
|||
factor = 1 |
|||
loop = l |
|||
while loop > 10 |
|||
factor *= 10 |
|||
loop = loop div 10 |
|||
. |
|||
while n > 0 |
|||
test += 1 |
|||
val = floor (factor * pow 10 (test * log mod 1)) |
|||
if val = l |
|||
n -= 1 |
|||
. |
|||
. |
|||
return test |
|||
. |
|||
proc test l n . . |
|||
print "p(" & l & ", " & n & ") = " & p l n |
|||
. |
|||
test 12 1 |
|||
test 12 2 |
|||
test 123 45 |
|||
test 123 12345 |
|||
test 123 678910 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
// First power of 2 that has specified leading decimal digits. Nigel Galloway: March 14th., 2021 |
|||
let fG n g=let fN l=let l=10.0**(l-floor l) in l>=n && l<g in let f=log10 2.0 in seq{1..0x0FFFFFFF}|>Seq.filter(float>>(*)f>>fN) |
|||
printfn "p(23,1)->%d" (int(Seq.item 0 (fG 2.3 2.4))) |
|||
printfn "p(99,1)->%d" (int(Seq.item 0 (fG 9.9 10.0))) |
|||
printfn "p(12,1)->%d" (int(Seq.item 0 (fG 1.2 1.3))) |
|||
printfn "p(12,2)->%d" (int(Seq.item 1 (fG 1.2 1.3))) |
|||
printfn "p(123,45)->%d" (int(Seq.item 44 (fG 1.23 1.24))) |
|||
printfn "p(123,12345)->%d" (int(Seq.item 12344 (fG 1.23 1.24))) |
|||
printfn "p(123,678910)->%d" (int(Seq.item 678909 (fG 1.23 1.24))) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
p(23,1)->61 |
|||
p(99,1)->93 |
|||
p(12,1)->7 |
|||
p(12,2)->80 |
|||
p(123,45)->12710 |
|||
p(123,12345)->3510491 |
|||
p(123,678910)->193060223 |
|||
Real: 00:00:10.140 |
|||
</pre> |
</pre> |
||
Line 102: | Line 559: | ||
{{trans|Pascal}} |
{{trans|Pascal}} |
||
{{works with|Factor|0.99 2019-10-06}} |
{{works with|Factor|0.99 2019-10-06}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting fry generalizations kernel literals math |
||
math.functions math.parser sequences tools.time ; |
math.functions math.parser sequences tools.time ; |
||
Line 123: | Line 580: | ||
123 678910 |
123 678910 |
||
[ 2dup p "%d %d p = %d\n" printf ] 2 5 mnapply |
[ 2dup p "%d %d p = %d\n" printf ] 2 5 mnapply |
||
] time</ |
] time</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 133: | Line 590: | ||
Running time: 44.208249282 seconds |
Running time: 44.208249282 seconds |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">#define FAC 0.30102999566398119521373889472449302677 |
|||
function p( L as uinteger, n as uinteger ) as uinteger |
|||
dim as uinteger count, j = 0 |
|||
dim as double x, y |
|||
dim as string digits, LS = str(L) |
|||
while count < n |
|||
j+=1 |
|||
x = FAC * j |
|||
if x < len(LS) then continue while |
|||
y = 10^(x-int(x)) |
|||
y *= 10^len(LS) |
|||
digits = str(y) |
|||
if left(digits,len(LS)) = LS then count += 1 |
|||
wend |
|||
return j |
|||
end function |
|||
print p(12, 1) |
|||
print p(12, 2) |
|||
print p(123, 45) |
|||
print p(123, 12345) |
|||
print p(123, 678910)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
7 |
|||
80 |
|||
12710 |
|||
3510491 |
|||
193060223</pre> |
|||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="futurebasic"> |
|||
local fn p( l as NSInteger, n as NSInteger ) as NSInteger |
|||
NSInteger test = 0, factor = 1, loop = l |
|||
double logv = log(2.0) / log(10.0) |
|||
while ( loop > 10 ) |
|||
factor *= 10 |
|||
loop /= 10 |
|||
wend |
|||
while ( n > 0 ) |
|||
NSInteger v |
|||
test++ |
|||
v = (NSInteger)( factor * fn pow( 10.0, fn fmod( test * logv, 1 ) ) ) |
|||
if ( v == l ) then n-- |
|||
wend |
|||
end fn = test |
|||
void local fn RunTest( l as NSInteger, n as NSInteger ) |
|||
printf @"fn p( %d, %d ) = %d", l, n, fn p( l, n ) |
|||
end fn |
|||
fn RunTest( 12, 1 ) |
|||
fn RunTest( 12, 2 ) |
|||
fn RunTest( 123, 45 ) |
|||
fn RunTest( 123, 12345 ) |
|||
fn RunTest( 123, 678910 ) |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
fn p( 12, 1 ) = 7 |
|||
fn p( 12, 2 ) = 80 |
|||
fn p( 123, 45 ) = 12710 |
|||
fn p( 123, 12345 ) = 3510491 |
|||
fn p( 123, 678910 ) = 193060223 |
|||
</pre> |
|||
=={{header|Gambas}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vbnet">Public Sub Main() |
|||
Print p(12, 1) |
|||
Print p(12, 2) |
|||
Print p(123, 45) |
|||
Print p(123, 12345) |
|||
Print p(123, 678910) |
|||
End |
|||
Function p(L As Integer, n As Integer) As Integer |
|||
Dim FAC As Float = 0.30102999566398119521373889472449302677 |
|||
Dim count As Integer, j As Integer = 0 |
|||
Dim x As Float, y As Float |
|||
Dim digits As String, LS As String = Str(L) |
|||
While count < n |
|||
j += 1 |
|||
x = FAC * j |
|||
If x < Len(LS) Then Continue |
|||
y = 10 ^ (x - CInt(x)) |
|||
y *= 10 ^ Len(LS) |
|||
digits = Str(y) |
|||
If Left(digits, Len(LS)) = LS Then count += 1 |
|||
Wend |
|||
Return j |
|||
End Function</syntaxhighlight> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Pascal}} |
{{trans|Pascal}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 179: | Line 740: | ||
} |
} |
||
fmt.Printf("\nTook %s\n", time.Since(start)) |
fmt.Printf("\nTook %s\n", time.Since(start)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 193: | Line 754: | ||
or, translating the alternative Pascal version as well, for good measure: |
or, translating the alternative Pascal version as well, for good measure: |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 259: | Line 820: | ||
} |
} |
||
fmt.Printf("\nTook %s\n", time.Since(start)) |
fmt.Printf("\nTook %s\n", time.Since(start)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 271: | Line 832: | ||
Took 1.422321658s |
Took 1.422321658s |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="haskell">import Control.Monad (guard) |
|||
import Text.Printf (printf) |
|||
p :: Int -> Int -> Int |
|||
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)]</syntaxhighlight> |
|||
Which, desugaring a little from Control.Monad (guard) and the do syntax, could also be rewritten as: |
|||
<syntaxhighlight lang="haskell">import Text.Printf (printf) |
|||
p :: Int -> Int -> Int |
|||
p l n = ([-1 ..] >>= f) !! pred n |
|||
where |
|||
digitCount = |
|||
floor $ |
|||
logBase 10 (fromIntegral l :: Float) |
|||
log10pwr = logBase 10 2 |
|||
f raised = [ds | l == ds] |
|||
where |
|||
ds = |
|||
floor $ |
|||
10 |
|||
** ( snd |
|||
( properFraction $ |
|||
log10pwr * realToFrac raised |
|||
) |
|||
+ realToFrac digitCount |
|||
) |
|||
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) |
|||
]</syntaxhighlight> |
|||
{{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. |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
p=: adverb define |
p=: adverb define |
||
: |
: |
||
Line 291: | Line 913: | ||
raised |
raised |
||
) |
) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Line 303: | Line 925: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java"> |
||
public class FirstPowerOfTwo { |
public class FirstPowerOfTwo { |
||
Line 338: | Line 960: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 348: | Line 970: | ||
</pre> |
</pre> |
||
=={{header|jq}}== |
|||
This solution uses unbounded-precision integers represented as arrays |
|||
of decimal digits beginning with the least significant digit, |
|||
e.g. [1,2,3] represents 321. |
|||
To speed up the computation, a variable limit on the number of significant digits |
|||
is used. Details can be seen in the implementation of p/2; for example, |
|||
for p(123, 678910) the number of significant digits starts off at (10 + 30) = 40 |
|||
and gradually tapers off to 10. |
|||
(Starting with (8+28) and tapering off to 8 is insufficient.) |
|||
<syntaxhighlight lang="jq">def normalize_base($base): |
|||
def n: |
|||
if length == 1 and .[0] < $base then .[0] |
|||
else .[0] % $base, |
|||
((.[0] / $base|floor) as $carry |
|||
|.[1:] |
|||
| .[0] += $carry |
|||
| n ) |
|||
end; |
|||
n; |
|||
def integers_as_arrays_times($n; $base): |
|||
map(. * $n) |
|||
| [normalize_base($base)]; |
|||
def p($L; $n): |
|||
# @assert($L > 0 and $n > 0) |
|||
($L|tostring|explode|reverse|map(. - 48)) as $digits # "0" is 48 |
|||
| ($digits|length) as $ndigits |
|||
| (2*(2+($n|log|floor))) as $extra |
|||
| { m: $n, |
|||
i: 0, |
|||
keep: ( 2*(2+$ndigits) + $extra), |
|||
p: [1] # reverse-array representation of 1 |
|||
} |
|||
| until(.m == 0; |
|||
.i += 1 |
|||
| .p |= integers_as_arrays_times(2; 10) |
|||
| .p = .p[ -(.keep) :] |
|||
| if (.p[-$ndigits:]) == $digits |
|||
then |
|||
| .m += -1 | .keep -= ($extra/$n) |
|||
else . end ) |
|||
| .i; |
|||
## The task |
|||
[[12, 1], [12, 2], [123, 45], [123, 12345], [123, 678910]][] |
|||
| "With L = \(.[0]) and n = \(.[1]), p(L, n) = \( p(.[0]; .[1]))" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
As for Julia. |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">function p(L, n) |
||
@assert(L > 0 && n > 0) |
@assert(L > 0 && n > 0) |
||
places, logof2, nfound = trunc(log(10, L)), log(10, 2), 0 |
places, logof2, nfound = trunc(log(10, L)), log(10, 2), 0 |
||
Line 362: | Line 1,037: | ||
println("With L = $L and n = $n, p(L, n) = ", p(L, n)) |
println("With L = $L and n = $n, p(L, n) = ", p(L, n)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
With L = 12 and n = 1, p(L, n) = 7 |
With L = 12 and n = 1, p(L, n) = 7 |
||
Line 373: | Line 1,048: | ||
===Faster version=== |
===Faster version=== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="julia">using Formatting, BenchmarkTools |
||
function p(L, n) |
function p(L, n) |
||
Line 413: | Line 1,088: | ||
testpLn(true) |
testpLn(true) |
||
@btime testpLn(false) |
@btime testpLn(false) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
With L = 12 and n = 1, p(L, n) = 7 |
With L = 12 and n = 1, p(L, n) = 7 |
||
Line 425: | Line 1,100: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">import kotlin.math.ln |
||
import kotlin.math.pow |
import kotlin.math.pow |
||
Line 459: | Line 1,134: | ||
} |
} |
||
return test |
return test |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p(12, 1) = 7 |
<pre>p(12, 1) = 7 |
||
Line 466: | Line 1,141: | ||
p(123, 12345) = 3,510,491 |
p(123, 12345) = 3,510,491 |
||
p(123, 678910) = 193,060,223</pre> |
p(123, 678910) = 193,060,223</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
Without compilation arbitrary precision will be used, and the algorithm will be slow, compiled is much faster: |
|||
<syntaxhighlight lang="mathematica">f = Compile[{{ll, _Integer}, {n, _Integer}}, |
|||
Module[{l, digitcount, log10power, raised, found, firstdigits, pwr = 2}, |
|||
l = Abs[ll]; |
|||
digitcount = Floor[Log[10, l]]; |
|||
log10power = Log[10, pwr]; |
|||
raised = -1; |
|||
found = 0; |
|||
While[found < n, |
|||
raised++; |
|||
firstdigits = Floor[10^(FractionalPart[log10power raised] + digitcount)]; |
|||
If[firstdigits == l, |
|||
found += 1; |
|||
] |
|||
]; |
|||
Return[raised] |
|||
] |
|||
]; |
|||
f[12, 1] |
|||
f[12, 2] |
|||
f[123, 45] |
|||
f[123, 12345] |
|||
f[123, 678910]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7 |
|||
80 |
|||
12710 |
|||
3510491 |
|||
193060223</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|Pascal}} |
|||
This is a translation to Nim of the very efficient Pascal alternative algorithm, with minor adjustments. |
|||
<syntaxhighlight lang="nim">import math, strformat |
|||
const |
|||
Lfloat64 = pow(2.0, 64) |
|||
Log10_2_64 = int(Lfloat64 * log10(2.0)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func ordinal(n: int): string = |
|||
case n |
|||
of 1: "1st" |
|||
of 2: "2nd" |
|||
of 3: "3rd" |
|||
else: $n & "th" |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc findExp(number, countLimit: int) = |
|||
var i = number |
|||
var digits = 1 |
|||
while i >= 10: |
|||
digits *= 10 |
|||
i = i div 10 |
|||
var lmtLower, lmtUpper: uint64 |
|||
var log10num = log10((number + 1) / digits) |
|||
if log10num >= 0.5: |
|||
lmtUpper = if (number + 1) / digits < 10: uint(log10Num * (Lfloat64 * 0.5)) * 2 + uint(log10Num * 2) |
|||
else: 0 |
|||
log10Num = log10(number / digits) |
|||
lmtLower = uint(log10Num * (Lfloat64 * 0.5)) * 2 + uint(log10Num * 2) |
|||
else: |
|||
lmtUpper = uint(log10Num * Lfloat64) |
|||
lmtLower = uint(log10(number / digits) * Lfloat64) |
|||
var count = 0 |
|||
var frac64 = 0u64 |
|||
var p = 0 |
|||
if lmtUpper != 0: |
|||
while true: |
|||
inc p |
|||
inc frac64, Log10_2_64 |
|||
if frac64 in lmtLower..lmtUpper: |
|||
inc count |
|||
if count >= countLimit: |
|||
break |
|||
else: |
|||
# Searching for "999...". |
|||
while true: |
|||
inc p |
|||
inc frac64, Log10_2_64 |
|||
if frac64 >= lmtLower: |
|||
inc count |
|||
if count >= countLimit: |
|||
break |
|||
echo fmt"""The {ordinal(count)} occurrence of 2 raised to a power""" & |
|||
fmt""" whose product starts with "{number}" is {p}""" |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
findExp(12, 1) |
|||
findExp(12, 2) |
|||
findExp(123, 45) |
|||
findExp(123, 12345) |
|||
findExp(123, 678910)</syntaxhighlight> |
|||
{{out}} |
|||
Processor: Core I5 8250U |
|||
Compilation command: <code>nim c -d:danger --passC:-flto leading12.nim</code> |
|||
Time: about 110 ms |
|||
<pre>The 1st occurrence of 2 raised to a power whose product starts with "12" is 7 |
|||
The 2nd 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 12710 |
|||
The 12345th occurrence of 2 raised to a power whose product starts with "123" is 3510491 |
|||
The 678910th occurrence of 2 raised to a power whose product starts with "123" is 193060223</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
Line 472: | Line 1,264: | ||
<b>0<= base ** frac(x) < base </b> thats 1 digit before the comma<Br> |
<b>0<= base ** frac(x) < base </b> thats 1 digit before the comma<Br> |
||
Only the first digits are needed.So I think, the accuracy is sufficient, because the results are the same :-) |
Only the first digits are needed.So I think, the accuracy is sufficient, because the results are the same :-) |
||
< |
<syntaxhighlight lang="pascal">program Power2FirstDigits; |
||
uses |
uses |
||
sysutils, |
sysutils, |
||
strUtils; |
|||
const |
const |
||
{$IFDEF FPC} |
|||
ld10= ln(2)/ln(10);// thats 1/log2(10) |
|||
{$MODE DELPHI} |
|||
ld10 :double = ln(2)/ln(10);// thats 1/log2(10) |
|||
function FindExp(CntLmt,Number:NativeUint):NativeUint; |
|||
{$ELSE} |
|||
ld10 = 0.30102999566398119521373889472449; |
|||
function Numb2USA(const S: string): string; |
|||
var |
var |
||
i, |
i, NA: Integer; |
||
begin |
begin |
||
i := Length(S); |
|||
//calc how many Digits needed |
|||
Result := S; |
|||
NA := 0; |
|||
while (i > 0) do |
|||
begin |
|||
if ((Length(Result) - i + 1 - NA) mod 3 = 0) and (i <> 1) then |
|||
begin |
|||
insert(',', Result, i); |
|||
inc(NA); |
|||
end; |
|||
Dec(i); |
|||
end; |
|||
end; |
|||
{$ENDIF} |
|||
function FindExp(CntLmt, Number: NativeUint): NativeUint; |
|||
var |
|||
i, cnt, DgtShift: NativeUInt; |
|||
begin |
|||
//calc how many Digits needed |
|||
i := Number; |
i := Number; |
||
DgtShift:= 1; |
DgtShift := 1; |
||
while i >= 10 do |
while i >= 10 do |
||
begin |
|||
DgtShift |
DgtShift := DgtShift * 10; |
||
i := i div 10; |
i := i div 10; |
||
end; |
end; |
||
Line 498: | Line 1,317: | ||
// x= i*ld10 -> 2^I = 10^x |
// x= i*ld10 -> 2^I = 10^x |
||
// 10^frac(x) -> [0..10[ = exp(ln(10)*frac(i*lD10)) |
// 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); |
inc(cnt); |
||
if cnt >= CntLmt then |
|||
BREAK; |
BREAK; |
||
end; |
end; |
||
until false; |
until false; |
||
write('The ',Numb2USA(IntToStr(cnt)),'th occurrence of 2 raised to a power'); |
write('The ', Numb2USA(IntToStr(cnt)), 'th occurrence of 2 raised to a power'); |
||
write(' whose product starts with "',Numb2USA(IntToStr( |
write(' whose product starts with "', Numb2USA(IntToStr(Number))); |
||
writeln('" is ',Numb2USA(IntToStr(i))); |
writeln('" is ', Numb2USA(IntToStr(i))); |
||
FindExp := i; |
FindExp := i; |
||
end; |
end; |
||
begin |
|||
Begin |
|||
FindExp(1,12); |
FindExp(1, 12); |
||
FindExp(2,12); |
FindExp(2, 12); |
||
FindExp(45,123); |
FindExp(45, 123); |
||
FindExp(12345,123); |
FindExp(12345, 123); |
||
FindExp(678910,123); |
FindExp(678910, 123); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 534: | Line 1,353: | ||
Logarithm (Ln(Number/Digits)/ln(10) <= frac(i*lD10) < ln((Number+1)/Digits)/ln(10) => no exp<BR> |
Logarithm (Ln(Number/Digits)/ln(10) <= frac(i*lD10) < ln((Number+1)/Digits)/ln(10) => no exp<BR> |
||
< |
<syntaxhighlight lang="pascal">program Power2Digits; |
||
uses |
uses |
||
sysutils,strUtils; |
sysutils,strUtils; |
||
Line 621: | Line 1,440: | ||
FindExp(1,99); |
FindExp(1,99); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The 1th occurrence of 2 raised to a power whose product starts with "12" is 7 |
<pre>The 1th occurrence of 2 raised to a power whose product starts with "12" is 7 |
||
Line 634: | Line 1,453: | ||
//32Bit |
//32Bit |
||
real 0m0,389s</pre> |
real 0m0,389s</pre> |
||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
function p(L,n: integer): integer; |
|||
begin |
|||
var logof2 := log10(2); |
|||
var places := trunc(log10(L)); |
|||
var nfound := 0; |
|||
var i := 1; |
|||
while True do |
|||
begin |
|||
var a := i * logof2; |
|||
var b := trunc(power(10,a-trunc(a)+places)); |
|||
if L = b then |
|||
begin |
|||
nfound += 1; |
|||
if nfound = n then break |
|||
end; |
|||
i += 1; |
|||
end; |
|||
Result := i; |
|||
end; |
|||
begin |
|||
foreach var (L,n) in Arr((12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)) do |
|||
Println($'p({n},{L}) = {p(n, L)}') |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
p(1,12) = 40 |
|||
p(2,12) = 58 |
|||
p(45,123) = 12868 |
|||
p(12345,123) = 3398841 |
|||
p(678910,123) = 188197328 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 699: | Line 1,554: | ||
printf "%-15s %9s power of two (2^n) that starts with %5s is at n = %s\n", "p($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); |
comma($nth) . ordinal_digit($nth), "'$prefix'", comma p($prefix, $nth); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p(12, 1): 1st power of two (2^n) that starts with '12' is at n = 7 |
<pre>p(12, 1): 1st power of two (2^n) that starts with '12' is at n = 7 |
||
Line 708: | Line 1,563: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/mpfr}} |
|||
<lang Phix>function p(integer L, n) |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
atom logof2 = log10(2) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer places = trunc(log10(L)), |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">L</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
nfound = 0, i = 1 |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">logof2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">log10</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
while true do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">places</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">log10</span><span style="color: #0000FF;">(</span><span style="color: #000000;">L</span><span style="color: #0000FF;">)),</span> |
|||
atom a = i * logof2, |
|||
<span style="color: #000000;">nfound</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
b = trunc(power(10,a-trunc(a)+places)) |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
if L == b then |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">logof2</span><span style="color: #0000FF;">,</span> |
|||
nfound += 1 |
|||
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">trunc</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">places</span><span style="color: #0000FF;">))</span> |
|||
if nfound == n then exit end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">L</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">b</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">nfound</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
i += 1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">nfound</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return i |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> |
|||
constant tests = {{12, 1}, {12, 2}, {123, 45}, {123, 12345}, {123, 678910}} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
include ordinal.e |
|||
include mpfr.e |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">123</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">123</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12345</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">123</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">678910</span><span style="color: #0000FF;">}}</span> |
|||
mpz z = mpz_init() |
|||
<span style="color: #008080;">include</span> <span style="color: #7060A8;">ordinal</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
for i=1 to length(tests) do |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
integer {L,n} = tests[i], pln = p(L,n) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
mpz_ui_pow_ui(z,2,pln) |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
integer digits = mpz_sizeinbase(z,10) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)-(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span> |
|||
string st = iff(digits>2e6?sprintf("%,d digits",digits): |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">L</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">pln</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">L</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
shorten(mpz_get_str(z),"digits",5)) |
|||
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pln</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"The %d%s power of 2 that starts with %d is %d [i.e. %s]\n",{n,ord(n),L,pln,st}) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_sizeinbase</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
end for</lang> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">></span><span style="color: #000000;">2e6</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%,d digits"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">):</span> |
|||
<span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"digits"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %d%s power of 2 that starts with %d is %d [i.e. %s]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">L</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">st</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 744: | Line 1,605: | ||
The 678910th power of 2 that starts with 123 is 193060223 [i.e. 58,116,919 digits] |
The 678910th power of 2 that starts with 123 is 193060223 [i.e. 58,116,919 digits] |
||
</pre> |
</pre> |
||
<small>(The last two tests are simply too much for pwa/p2js)</small> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Using logs, as seen first in the Pascal example. |
Using logs, as seen first in the Pascal example. |
||
< |
<syntaxhighlight lang="python">from math import log, modf, floor |
||
def p(l, n, pwr=2): |
def p(l, n, pwr=2): |
||
Line 765: | Line 1,627: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
for l, n in [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]: |
for l, n in [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]: |
||
print(f"p({l}, {n}) =", p(l, n))</ |
print(f"p({l}, {n}) =", p(l, n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 773: | Line 1,635: | ||
p(123, 12345) = 3510491 |
p(123, 12345) = 3510491 |
||
p(123, 678910) = 193060223</pre> |
p(123, 678910) = 193060223</pre> |
||
=={{header|Racket}}== |
|||
{{trans|Pascal}} |
|||
First implementation is an untyped, naive revision of the Pascal algorithm. |
|||
But there is a lot of casting between the exact integers an floats. As well as runtime type checking. |
|||
Then there is the typed racket version, which is stricter about the use of types |
|||
(although, I'm not super happy at the algorithm counting using floating-point integers... but it's faster) |
|||
Compare and contrast... |
|||
===Untyped Racket=== |
|||
<syntaxhighlight lang="racket">#lang racket |
|||
(define (fract-part f) |
|||
(- f (truncate f))) |
|||
(define ln10 (log 10)) |
|||
(define ln2/ln10 (/ (log 2) ln10)) |
|||
(define (inexact-p-test L) |
|||
(let ((digit-shift (let loop ((L (quotient L 10)) (shift 1)) |
|||
(if (zero? L) shift (loop (quotient L 10) (* 10 shift)))))) |
|||
(λ (p) (= L (truncate (* digit-shift (exp (* ln10 (fract-part (* p ln2/ln10)))))))))) |
|||
(define (p L n) |
|||
(let ((test? (inexact-p-test L))) |
|||
(let loop ((j 1) (n (sub1 n))) |
|||
(cond [(not (test? j)) (loop (add1 j) n)] |
|||
[(zero? n) j] |
|||
[else (loop (add1 j) (sub1 n))])))) |
|||
(module+ main |
|||
(define (report-p L n) |
|||
(time (printf "p(~a, ~a) = ~a~%" L n (p L n)))) |
|||
(report-p 12 1) |
|||
(report-p 12 2) |
|||
(report-p 123 45) |
|||
(report-p 123 12345) |
|||
(report-p 123 678910))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>p(12, 1) = 7 |
|||
cpu time: 1 real time: 1 gc time: 0 |
|||
p(12, 2) = 80 |
|||
cpu time: 0 real time: 0 gc time: 0 |
|||
p(123, 45) = 12710 |
|||
cpu time: 5 real time: 5 gc time: 0 |
|||
p(123, 12345) = 3510491 |
|||
cpu time: 439 real time: 442 gc time: 23 |
|||
p(123, 678910) = 193060223 |
|||
cpu time: 27268 real time: 27354 gc time: 194</pre> |
|||
===Typed Racket=== |
|||
<syntaxhighlight lang="racket">#lang typed/racket |
|||
(: fract-part (-> Float Float)) |
|||
(: ln10 Positive-Float) |
|||
(: ln2/ln10 Positive-Float) |
|||
(: p (-> Positive-Index Positive-Index Positive-Integer)) |
|||
(define (fract-part f) |
|||
(- f (truncate f))) |
|||
(define ln10 (cast (log 10) Positive-Float)) |
|||
(define ln2/ln10 (cast (/ (log 2) ln10) Positive-Float)) |
|||
(define (inexact-p-test [L : Positive-Index]) |
|||
(let ((digit-shift : Nonnegative-Float |
|||
(let loop ((L (quotient L 10)) (shift : Nonnegative-Float 1.)) |
|||
(if (zero? L) shift (loop (quotient L 10) (* 10. shift))))) |
|||
(l (exact->inexact L))) |
|||
(: f (-> Nonnegative-Float Boolean)) |
|||
(define (f p) (= l (truncate (* digit-shift (exp (* ln10 (fract-part (* p ln2/ln10)))))))) |
|||
f)) |
|||
(define (p L n) |
|||
(let ((test? (inexact-p-test L))) |
|||
(let loop : Positive-Integer ((j : Positive-Float 1.) (n : Index (sub1 n))) |
|||
(cond [(not (test? j)) (loop (add1 j) n)] |
|||
[(zero? n) (assert (exact-round j) positive?)] |
|||
[else (loop (add1 j) (sub1 n))])))) |
|||
(module+ main |
|||
(: report-p (-> Positive-Index Positive-Index Void)) |
|||
(define (report-p L n) |
|||
(time (printf "p(~a, ~a) = ~a~%" L n (p L n)))) |
|||
(report-p 12 1) |
|||
(report-p 12 2) |
|||
(report-p 123 45) |
|||
(report-p 123 12345) |
|||
(report-p 123 678910)) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>p(12, 1) = 7 |
|||
cpu time: 1 real time: 1 gc time: 0 |
|||
p(12, 2) = 80 |
|||
cpu time: 0 real time: 0 gc time: 0 |
|||
p(123, 45) = 12710 |
|||
cpu time: 5 real time: 5 gc time: 0 |
|||
p(123, 12345) = 3510491 |
|||
cpu time: 237 real time: 231 gc time: 31 |
|||
p(123, 678910) = 193060223 |
|||
cpu time: 10761 real time: 10794 gc time: 17</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 779: | Line 1,752: | ||
Uses logs similar to Go and Pascal entries. Takes advantage of patterns in the powers to cut out a bunch of calculations. |
Uses logs similar to Go and Pascal entries. Takes advantage of patterns in the powers to cut out a bunch of calculations. |
||
<lang |
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers; |
||
constant $ln2ln10 = log(2) / log(10); |
constant $ln2ln10 = log(2) / log(10); |
||
Line 814: | Line 1,787: | ||
printf "%-15s %9s power of two (2^n) that starts with %5s is at n = %s\n", "p($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); |
comma($nth) ~ ordinal-digit($nth).substr(*-2), "'$prefix'", comma p($prefix, $nth); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p(12, 1): 1st power of two (2^n) that starts with '12' is at n = 7 |
<pre>p(12, 1): 1st power of two (2^n) that starts with '12' is at n = 7 |
||
Line 823: | Line 1,796: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight 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*/ |
parse arg L n b . /*obtain optional arguments from the CL*/ |
||
if L=='' | L=="," then L= 12 /*Not specified? Then use the default.*/ |
if L=='' | L=="," then L= 12 /*Not specified? Then use the default.*/ |
||
Line 851: | Line 1,824: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
commas: arg _; do c=length(_)-3 to 1 by -3; _= insert(',', _, c); end; return _ |
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))</ |
th: arg _; return _ || word('th st nd rd', 1 +_//10 * (_//100 % 10\==1) * (_//10 <4))</syntaxhighlight> |
||
{{out|output|text= when using the inputs of: <tt> 12 1 </tt>}} |
{{out|output|text= when using the inputs of: <tt> 12 1 </tt>}} |
||
<pre> |
<pre> |
||
Line 872: | Line 1,845: | ||
The 678910th occurrence of 2 raised to a power whose product starts with "123' is 193,060,223. |
The 678910th occurrence of 2 raised to a power whose product starts with "123' is 193,060,223. |
||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
{{trans|C}} |
|||
{{works with|HP|48}} |
|||
The <code>6 RND</code> sequence is necessary on calculators, which do the math in simple precision. It can be removed when executing the program on a double precision emulator. |
|||
« SWAP DUP XPON ALOG 2 LOG → digits factor log2 |
|||
« 0 |
|||
'''WHILE''' OVER 0 > '''REPEAT''' |
|||
1 + |
|||
DUP log2 * FP ALOG 6 RND factor * IP |
|||
'''IF''' digits == '''THEN''' SWAP 1 - SWAP '''END''' |
|||
'''END''' |
|||
SWAP DROP |
|||
» » '<span style="color:blue">P</span>' STO |
|||
12 1 <span style="color:blue">P</span> |
|||
12 2 <span style="color:blue">P</span> |
|||
123 45 <span style="color:blue">P</span> |
|||
{{out}} |
|||
<pre> |
|||
3: 7 |
|||
2: 80 |
|||
1: 12710 |
|||
</pre> |
|||
The last result needs 29 minutes on a basic HP-48SX. |
|||
=={{header|Ruby}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="ruby">def p(l, n) |
|||
test = 0 |
|||
logv = Math.log(2.0) / Math.log(10.0) |
|||
factor = 1 |
|||
loopv = l |
|||
while loopv > 10 do |
|||
factor = factor * 10 |
|||
loopv = loopv / 10 |
|||
end |
|||
while n > 0 do |
|||
test = test + 1 |
|||
val = (factor * (10.0 ** ((test * logv).modulo(1.0)))).floor |
|||
if val == l then |
|||
n = n - 1 |
|||
end |
|||
end |
|||
return test |
|||
end |
|||
def runTest(l, n) |
|||
print "P(%d, %d) = %d\n" % [l, n, p(l, n)] |
|||
end |
|||
runTest(12, 1) |
|||
runTest(12, 2) |
|||
runTest(123, 45) |
|||
runTest(123, 12345) |
|||
runTest(123, 678910)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>P(12, 1) = 7 |
|||
P(12, 2) = 80 |
|||
P(123, 45) = 12710 |
|||
P(123, 12345) = 3510491 |
|||
P(123, 678910) = 193060223</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">fn power_of_two(l: isize, n: isize) -> isize { |
|||
let mut test: isize = 0; |
|||
let log: f64 = 2.0_f64.ln() / 10.0_f64.ln(); |
|||
let mut factor: isize = 1; |
|||
let mut looop = l; |
|||
let mut nn = n; |
|||
while looop > 10 { |
|||
factor *= 10; |
|||
looop /= 10; |
|||
} |
|||
while nn > 0 { |
|||
test = test + 1; |
|||
let val: isize = (factor as f64 * 10.0_f64.powf(test as f64 * log % 1.0)) as isize; |
|||
if val == l { |
|||
nn = nn - 1; |
|||
} |
|||
} |
|||
test |
|||
} |
|||
fn run_test(l: isize, n: isize) { |
|||
println!("p({}, {}) = {}", l, n, power_of_two(l, n)); |
|||
} |
|||
fn main() { |
|||
run_test(12, 1); |
|||
run_test(12, 2); |
|||
run_test(123, 45); |
|||
run_test(123, 12345); |
|||
run_test(123, 678910); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
p(12, 1) = 7 |
|||
p(12, 2) = 80 |
|||
p(123, 45) = 12710 |
|||
p(123, 12345) = 3510491 |
|||
p(123, 678910) = 193060223 |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">object FirstPowerOfTwo { |
|||
def p(l: Int, n: Int): Int = { |
|||
var n2 = n |
|||
var test = 0 |
|||
val log = math.log(2) / math.log(10) |
|||
var factor = 1 |
|||
var loop = l |
|||
while (loop > 10) { |
|||
factor *= 10 |
|||
loop /= 10 |
|||
} |
|||
while (n2 > 0) { |
|||
test += 1 |
|||
val value = (factor * math.pow(10, test * log % 1)).asInstanceOf[Int] |
|||
if (value == l) { |
|||
n2 -= 1 |
|||
} |
|||
} |
|||
test |
|||
} |
|||
def runTest(l: Int, n: Int): Unit = { |
|||
printf("p(%d, %d) = %,d%n", l, n, p(l, n)) |
|||
} |
|||
def main(args: Array[String]): Unit = { |
|||
runTest(12, 1) |
|||
runTest(12, 2) |
|||
runTest(123, 45) |
|||
runTest(123, 12345) |
|||
runTest(123, 678910) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func farey_approximations(r, callback) { |
||
var (a1 = r.int, b1 = 1) |
var (a1 = r.int, b1 = 1) |
||
Line 936: | Line 2,057: | ||
for a,b in (tests) { |
for a,b in (tests) { |
||
say "p(#{a}, #{b}) = #{p(a,b)}" |
say "p(#{a}, #{b}) = #{p(a,b)}" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 954: | Line 2,075: | ||
===Slower Version=== |
===Slower Version=== |
||
< |
<syntaxhighlight lang="swift">let ld10 = log(2.0) / log(10.0) |
||
func p(L: Int, n: Int) -> Int { |
func p(L: Int, n: Int) -> Int { |
||
Line 992: | Line 2,113: | ||
for (l, n) in cases { |
for (l, n) in cases { |
||
print("p(\(l), \(n)) = \(p(L: l, n: n))") |
print("p(\(l), \(n)) = \(p(L: l, n: n))") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,004: | Line 2,125: | ||
===Faster Version=== |
===Faster Version=== |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
func p2(L: Int, n: Int) -> Int { |
func p2(L: Int, n: Int) -> Int { |
||
Line 1,071: | Line 2,192: | ||
for (l, n) in cases { |
for (l, n) in cases { |
||
print("p(\(l), \(n)) = \(p2(L: l, n: n))") |
print("p(\(l), \(n)) = \(p2(L: l, n: n))") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Same as before. |
Same as before. |
||
=={{header|Visual Basic .NET}}== |
|||
<syntaxhighlight lang="vbnet">Module Module1 |
|||
Function Func(ByVal l As Integer, ByVal n As Integer) As Long |
|||
Dim res As Long = 0, f As Long = 1 |
|||
Dim lf As Double = Math.Log10(2) |
|||
Dim i As Integer = l |
|||
While i > 10 |
|||
f *= 10 |
|||
i /= 10 |
|||
End While |
|||
While n > 0 |
|||
res += 1 |
|||
If CInt((f * Math.Pow(10, res * lf Mod 1))) = l Then |
|||
n -= 1 |
|||
End If |
|||
End While |
|||
Return res |
|||
End Function |
|||
Sub Main() |
|||
Dim values = {Tuple.Create(12, 1), Tuple.Create(12, 2), Tuple.Create(123, 45), Tuple.Create(123, 12345), Tuple.Create(123, 678910), Tuple.Create(99, 1)} |
|||
For Each pair In values |
|||
Console.WriteLine("p({0,3}, {1,6}) = {2,11:n0}", pair.Item1, pair.Item2, Func(pair.Item1, pair.Item2)) |
|||
Next |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre>p( 12, 1) = 60 |
|||
p( 12, 2) = 70 |
|||
p(123, 45) = 12,710 |
|||
p(123, 12345) = 3,496,509 |
|||
p(123, 678910) = 192,278,374 |
|||
p( 99, 1) = 93</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-fmt}} |
|||
{{libheader|Wren-math}} |
|||
Just the first version which has turned out to be much quicker than the Go entry (around 28 seconds on the same machine). Frankly, I've no idea why. |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
import "./math" for Math |
|||
var ld10 = Math.ln2 / Math.ln10 |
|||
var p = Fn.new { |L, n| |
|||
var i = L |
|||
var digits = 1 |
|||
while (i >= 10) { |
|||
digits = digits * 10 |
|||
i = (i/10).floor |
|||
} |
|||
var count = 0 |
|||
i = 0 |
|||
while (count < n) { |
|||
var e = (Math.ln10 * (i * ld10).fraction).exp |
|||
if ((e * digits).truncate == L) count = count + 1 |
|||
i = i + 1 |
|||
} |
|||
return i - 1 |
|||
} |
|||
var start = System.clock |
|||
var params = [ [12, 1] , [12, 2], [123, 45], [123, 12345], [123, 678910] ] |
|||
for (param in params) { |
|||
Fmt.print("p($d, $d) = $,d", param[0], param[1], p.call(param[0], param[1])) |
|||
} |
|||
System.print("\nTook %(System.clock - start) seconds.")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 16.51308 seconds. |
|||
</pre> |
|||
=={{header|Yabasic}}== |
|||
<syntaxhighlight lang="yabasic">FAC = 0.30102999566398119521373889472449302677 |
|||
print p(12, 1) |
|||
print p(12, 2) |
|||
print p(123, 45) |
|||
print p(123, 12345) |
|||
print p(123, 678910) |
|||
end |
|||
sub p(L, n) |
|||
cont = 0 : j = 0 |
|||
LS$ = str$(L) |
|||
while cont < n |
|||
j = j + 1 |
|||
x = FAC * j |
|||
//if x < len(LS$) continue while 'sino da error |
|||
y = 10^(x-int(x)) |
|||
y = y * 10^len(LS$) |
|||
digits$ = str$(y) |
|||
if left$(digits$, len(LS$)) = LS$ cont = cont + 1 |
|||
end while |
|||
return j |
|||
end sub</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Pascal}} |
{{trans|Pascal}} |
||
Lots of float are slow so I've restricted the tests. |
Lots of float are slow so I've restricted the tests. |
||
< |
<syntaxhighlight lang="zkl">// float*int --> float and int*float --> int |
||
fcn p(L,nth){ // 2^j = <L><digits> |
fcn p(L,nth){ // 2^j = <L><digits> |
||
var [const] ln10=(10.0).log(), ld10=(2.0).log() / ln10; |
var [const] ln10=(10.0).log(), ld10=(2.0).log() / ln10; |
||
Line 1,089: | Line 2,321: | ||
return(i); |
return(i); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
||
GMP is just used to give some context on the size of the numbers we |
GMP is just used to give some context on the size of the numbers we |
||
are dealing with. |
are dealing with. |
||
< |
<syntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP |
||
tests:=T( T(12,1),T(12,2), T(123,45),T(123,12345), ); |
tests:=T( T(12,1),T(12,2), T(123,45),T(123,12345), ); |
||
foreach L,nth in (tests){ |
foreach L,nth in (tests){ |
||
Line 1,099: | Line 2,331: | ||
println("2^%-10,d is occurance %,d of 2^n == '%d<abc>' (%,d digits)" |
println("2^%-10,d is occurance %,d of 2^n == '%d<abc>' (%,d digits)" |
||
.fmt(n,nth,L,BI(2).pow(n).len())); |
.fmt(n,nth,L,BI(2).pow(n).len())); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 11:29, 6 August 2024
![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.
11l
F p(=l, n, pwr = 2)
l = Int(abs(l))
V digitcount = floor(log(l, 10))
V log10pwr = log(pwr, 10)
V (raised, found) = (-1, 0)
L found < n
raised++
V firstdigits = floor(10 ^ (fract(log10pwr * raised) + digitcount))
I firstdigits == l
found++
R raised
L(l, n) [(12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)]
print(‘p(’l‘, ’n‘) = ’p(l, n))
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
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).
# find values of p( L, n ) where p( L, n ) is the nth-smallest j such that #
# the decimal representation of 2^j starts with the digits of L #
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
- 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
BASIC256
global FAC
FAC = 0.30102999566398119521373889472449302677
print p(12, 1)
print p(12, 2)
print p(123, 45)
print p(123, 12345)
print p(123, 678910)
end
function p(L, n)
cont = 0 : j = 0
LS = string(L)
while cont < n
j += 1
x = FAC * j
if x < length(LS) then continue while
y = 10^(x-int(x))
y *= 10^length(LS)
digits = string(y)
if left(digits,length(LS)) = LS then cont += 1
end while
return j
end function
- Output:
Same as FreeBASIC entry.
C
#include <math.h>
#include <stdio.h>
int p(int l, int n) {
int test = 0;
double logv = log(2.0) / log(10.0);
int factor = 1;
int loop = l;
while (loop > 10) {
factor *= 10;
loop /= 10;
}
while (n > 0) {
int val;
test++;
val = (int)(factor * pow(10.0, fmod(test * logv, 1)));
if (val == l) {
n--;
}
}
return test;
}
void runTest(int l, int n) {
printf("p(%d, %d) = %d\n", l, n, p(l, n));
}
int main() {
runTest(12, 1);
runTest(12, 2);
runTest(123, 45);
runTest(123, 12345);
runTest(123, 678910);
return 0;
}
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
C++
// a mini chrestomathy solution
#include <string>
#include <chrono>
#include <cmath>
#include <locale>
using namespace std;
using namespace chrono;
// translated from java example
unsigned int js(int l, int n) {
unsigned int res = 0, f = 1;
double lf = log(2) / log(10), ip;
for (int i = l; i > 10; i /= 10) f *= 10;
while (n > 0)
if ((int)(f * pow(10, modf(++res * lf, &ip))) == l) n--;
return res;
}
// translated from go integer example (a.k.a. go translation of pascal alternative example)
unsigned int gi(int ld, int n) {
string Ls = to_string(ld);
unsigned int res = 0, count = 0; unsigned long long f = 1;
for (int i = 1; i <= 18 - Ls.length(); i++) f *= 10;
const unsigned long long ten18 = 1e18; unsigned long long probe = 1;
do {
probe <<= 1; res++; if (probe >= ten18) {
do {
if (probe >= ten18) probe /= 10;
if (probe / f == ld) if (++count >= n) { count--; break; }
probe <<= 1; res++;
} while (1);
}
string ps = to_string(probe);
if (ps.substr(0, min(Ls.length(), ps.length())) == Ls) if (++count >= n) break;
} while (1);
return res;
}
// translated from pascal alternative example
unsigned int pa(int ld, int n) {
const double L_float64 = pow(2, 64);
const unsigned long long Log10_2_64 = (unsigned long long)(L_float64 * log(2) / log(10));
double Log10Num; unsigned long long LmtUpper, LmtLower, Frac64;
int res = 0, dgts = 1, cnt;
for (int i = ld; i >= 10; i /= 10) dgts *= 10;
Log10Num = log((ld + 1.0) / dgts) / log(10);
// '316' was a limit
if (Log10Num >= 0.5) {
LmtUpper = (ld + 1.0) / dgts < 10.0 ? (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2) : 0;
Log10Num = log((double)ld / dgts) / log(10);
LmtLower = (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2);
} else {
LmtUpper = (unsigned long long)(Log10Num * L_float64);
LmtLower = (unsigned long long)(log((double)ld / dgts) / log(10) * L_float64);
}
cnt = 0; Frac64 = 0; if (LmtUpper != 0) {
do {
res++; Frac64 += Log10_2_64;
if ((Frac64 >= LmtLower) & (Frac64 < LmtUpper))
if (++cnt >= n) break;
} while (1);
} else { // '999..'
do {
res++; Frac64 += Log10_2_64;
if (Frac64 >= LmtLower) if (++cnt >= n) break;
} while (1);
};
return res;
}
int params[] = { 12, 1, 12, 2, 123, 45, 123, 12345, 123, 678910, 99, 1 };
void doOne(string name, unsigned int (*func)(int a, int b)) {
printf("%s version:\n", name.c_str());
auto start = steady_clock::now();
for (int i = 0; i < size(params); i += 2)
printf("p(%3d, %6d) = %'11u\n", params[i], params[i + 1], func(params[i], params[i + 1]));
printf("Took %f seconds\n\n", duration<double>(steady_clock::now() - start).count());
}
int main() {
setlocale(LC_ALL, "");
doOne("java simple", js);
doOne("go integer", gi);
doOne("pascal alternative", pa);
}
- Output:
Exeution times from Tio.run, language
java simple version: 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 p( 99, 1) = 93 Took 11.350696 seconds go integer version: 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 p( 99, 1) = 93 Took 1.787658 seconds pascal alternative version: 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 p( 99, 1) = 93 Took 0.299815 seconds
Execution times on a core i7-7700 @ 3.6Ghz, g++, compiler flags: -O3 -std=c++17
java simple version: ... Took 15.060563 seconds go integer version: ... Took 1.268436 seconds pascal alternative version: ... Took 0.082407 seconds
C#
// a mini chrestomathy solution
using System;
class Program {
// translated from java example
static long js(int l, int n) {
long res = 0, f = 1;
double lf = Math.Log10(2);
for (int i = l; i > 10; i /= 10) f *= 10;
while (n > 0)
if ((int)(f * Math.Pow(10, ++res * lf % 1)) == l) n--;
return res;
}
// translated from go integer example (a.k.a. go translation of pascal alternative example)
static long gi(int ld, int n) {
string Ls = ld.ToString();
long res = 0, count = 0, f = 1;
for (int i = 1; i <= 18 - Ls.Length; i++) f *= 10;
const long ten18 = (long)1e18; long probe = 1;
do {
probe <<= 1; res++; if (probe >= ten18)
do {
if (probe >= ten18) probe /= 10;
if (probe / f == ld)
if (++count >= n) { count--; break; }
probe <<= 1; res++;
} while (true);
string ps = probe.ToString();
if (ps.Substring(0, Math.Min(Ls.Length, ps.Length)) == Ls)
if (++count >= n) break;
} while (true);
return res;
}
// translated from pascal alternative example
static long pa(int ld, int n) {
double L_float64 = Math.Pow(2, 64);
ulong Log10_2_64 = (ulong)(L_float64 * Math.Log10(2));
double Log10Num; ulong LmtUpper, LmtLower, Frac64;
long res = 0, dgts = 1, cnt;
for (int i = ld; i >= 10; i /= 10) dgts *= 10;
Log10Num = Math.Log10((ld + 1.0) / dgts);
// '316' was a limit
if (Log10Num >= 0.5) {
LmtUpper = (ld + 1.0) / dgts < 10.0 ? (ulong)(Log10Num * (L_float64 * 0.5)) * 2 + (ulong)(Log10Num * 2) : 0;
Log10Num = Math.Log10((double)ld / dgts);
LmtLower = (ulong)(Log10Num * (L_float64 * 0.5)) * 2 + (ulong)(Log10Num * 2);
} else {
LmtUpper = (ulong)(Log10Num * L_float64);
LmtLower = (ulong)(Math.Log10((double)ld / dgts) * L_float64);
}
cnt = 0; Frac64 = 0; if (LmtUpper != 0)
do {
res++; Frac64 += Log10_2_64;
if ((Frac64 >= LmtLower) & (Frac64 < LmtUpper))
if (++cnt >= n) break;
} while (true);
else // '999..'
do {
res++; Frac64 += Log10_2_64;
if (Frac64 >= LmtLower) if (++cnt >= n) break;
} while (true);
return res;
}
static int[] values = new int[] { 12, 1, 12, 2, 123, 45, 123, 12345, 123, 678910, 99, 1 };
static void doOne(string name, Func<int, int, long> fun) {
Console.WriteLine("{0} version:", name);
var start = DateTime.Now;
for (int i = 0; i < values.Length; i += 2)
Console.WriteLine("p({0,3}, {1,6}) = {2,11:n0}", values[i], values[i + 1], fun(values[i], values[i + 1]));
Console.WriteLine("Took {0} seconds\n", DateTime.Now - start);
}
static void Main() {
doOne("java simple", js);
doOne("go integer", gi);
doOne("pascal alternative", pa);
}
}
- Output:
Results on the core i7-7700 @ 3.6Ghz.
java simple version: 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 p( 99, 1) = 93 Took 00:00:09.5992122 seconds go integer version: 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 p( 99, 1) = 93 Took 00:00:01.5335699 seconds pascal alternative version: 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 p( 99, 1) = 93 Took 00:00:00.1391226 seconds
D
import std.math;
import std.stdio;
int p(int l, int n) {
int test = 0;
double logv = log(2.0) / log(10.0);
int factor = 1;
int loop = l;
while (loop > 10) {
factor *= 10;
loop /= 10;
}
while (n > 0) {
int val;
test++;
val = cast(int)(factor * pow(10.0, fmod(test * logv, 1)));
if (val == l) {
n--;
}
}
return test;
}
void runTest(int l, int n) {
writefln("p(%d, %d) = %d", l, n, p(l, n));
}
void main() {
runTest(12, 1);
runTest(12, 2);
runTest(123, 45);
runTest(123, 12345);
runTest(123, 678910);
}
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
Delphi
See Pascal.
EasyLang
func p l n .
log = log10 2
factor = 1
loop = l
while loop > 10
factor *= 10
loop = loop div 10
.
while n > 0
test += 1
val = floor (factor * pow 10 (test * log mod 1))
if val = l
n -= 1
.
.
return test
.
proc test l n . .
print "p(" & l & ", " & n & ") = " & p l n
.
test 12 1
test 12 2
test 123 45
test 123 12345
test 123 678910
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
F#
// First power of 2 that has specified leading decimal digits. Nigel Galloway: March 14th., 2021
let fG n g=let fN l=let l=10.0**(l-floor l) in l>=n && l<g in let f=log10 2.0 in seq{1..0x0FFFFFFF}|>Seq.filter(float>>(*)f>>fN)
printfn "p(23,1)->%d" (int(Seq.item 0 (fG 2.3 2.4)))
printfn "p(99,1)->%d" (int(Seq.item 0 (fG 9.9 10.0)))
printfn "p(12,1)->%d" (int(Seq.item 0 (fG 1.2 1.3)))
printfn "p(12,2)->%d" (int(Seq.item 1 (fG 1.2 1.3)))
printfn "p(123,45)->%d" (int(Seq.item 44 (fG 1.23 1.24)))
printfn "p(123,12345)->%d" (int(Seq.item 12344 (fG 1.23 1.24)))
printfn "p(123,678910)->%d" (int(Seq.item 678909 (fG 1.23 1.24)))
- Output:
p(23,1)->61 p(99,1)->93 p(12,1)->7 p(12,2)->80 p(123,45)->12710 p(123,12345)->3510491 p(123,678910)->193060223 Real: 00:00:10.140
Factor
A translation of the first Pascal example:
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
- 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
FreeBASIC
#define FAC 0.30102999566398119521373889472449302677
function p( L as uinteger, n as uinteger ) as uinteger
dim as uinteger count, j = 0
dim as double x, y
dim as string digits, LS = str(L)
while count < n
j+=1
x = FAC * j
if x < len(LS) then continue while
y = 10^(x-int(x))
y *= 10^len(LS)
digits = str(y)
if left(digits,len(LS)) = LS then count += 1
wend
return j
end function
print p(12, 1)
print p(12, 2)
print p(123, 45)
print p(123, 12345)
print p(123, 678910)
- Output:
7 80 12710 3510491 193060223
FutureBasic
local fn p( l as NSInteger, n as NSInteger ) as NSInteger
NSInteger test = 0, factor = 1, loop = l
double logv = log(2.0) / log(10.0)
while ( loop > 10 )
factor *= 10
loop /= 10
wend
while ( n > 0 )
NSInteger v
test++
v = (NSInteger)( factor * fn pow( 10.0, fn fmod( test * logv, 1 ) ) )
if ( v == l ) then n--
wend
end fn = test
void local fn RunTest( l as NSInteger, n as NSInteger )
printf @"fn p( %d, %d ) = %d", l, n, fn p( l, n )
end fn
fn RunTest( 12, 1 )
fn RunTest( 12, 2 )
fn RunTest( 123, 45 )
fn RunTest( 123, 12345 )
fn RunTest( 123, 678910 )
HandleEvents
- Output:
fn p( 12, 1 ) = 7 fn p( 12, 2 ) = 80 fn p( 123, 45 ) = 12710 fn p( 123, 12345 ) = 3510491 fn p( 123, 678910 ) = 193060223
Gambas
Public Sub Main()
Print p(12, 1)
Print p(12, 2)
Print p(123, 45)
Print p(123, 12345)
Print p(123, 678910)
End
Function p(L As Integer, n As Integer) As Integer
Dim FAC As Float = 0.30102999566398119521373889472449302677
Dim count As Integer, j As Integer = 0
Dim x As Float, y As Float
Dim digits As String, LS As String = Str(L)
While count < n
j += 1
x = FAC * j
If x < Len(LS) Then Continue
y = 10 ^ (x - CInt(x))
y *= 10 ^ Len(LS)
digits = Str(y)
If Left(digits, Len(LS)) = LS Then count += 1
Wend
Return j
End Function
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))
}
- 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:
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))
}
- 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
import Control.Monad (guard)
import Text.Printf (printf)
p :: Int -> Int -> Int
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)]
Which, desugaring a little from Control.Monad (guard) and the do syntax, could also be rewritten as:
import Text.Printf (printf)
p :: Int -> Int -> Int
p l n = ([-1 ..] >>= f) !! pred n
where
digitCount =
floor $
logBase 10 (fromIntegral l :: Float)
log10pwr = logBase 10 2
f raised = [ds | l == ds]
where
ds =
floor $
10
** ( snd
( properFraction $
log10pwr * realToFrac raised
)
+ realToFrac digitCount
)
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)
]
- 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.
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
)
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
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;
}
}
- 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
jq
This solution uses unbounded-precision integers represented as arrays of decimal digits beginning with the least significant digit, e.g. [1,2,3] represents 321.
To speed up the computation, a variable limit on the number of significant digits is used. Details can be seen in the implementation of p/2; for example, for p(123, 678910) the number of significant digits starts off at (10 + 30) = 40 and gradually tapers off to 10.
(Starting with (8+28) and tapering off to 8 is insufficient.)
def normalize_base($base):
def n:
if length == 1 and .[0] < $base then .[0]
else .[0] % $base,
((.[0] / $base|floor) as $carry
|.[1:]
| .[0] += $carry
| n )
end;
n;
def integers_as_arrays_times($n; $base):
map(. * $n)
| [normalize_base($base)];
def p($L; $n):
# @assert($L > 0 and $n > 0)
($L|tostring|explode|reverse|map(. - 48)) as $digits # "0" is 48
| ($digits|length) as $ndigits
| (2*(2+($n|log|floor))) as $extra
| { m: $n,
i: 0,
keep: ( 2*(2+$ndigits) + $extra),
p: [1] # reverse-array representation of 1
}
| until(.m == 0;
.i += 1
| .p |= integers_as_arrays_times(2; 10)
| .p = .p[ -(.keep) :]
| if (.p[-$ndigits:]) == $digits
then
| .m += -1 | .keep -= ($extra/$n)
else . end )
| .i;
## The task
[[12, 1], [12, 2], [123, 45], [123, 12345], [123, 678910]][]
| "With L = \(.[0]) and n = \(.[1]), p(L, n) = \( p(.[0]; .[1]))"
- Output:
As for Julia.
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
- 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
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)
- 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
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
}
- 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
Mathematica /Wolfram Language
Without compilation arbitrary precision will be used, and the algorithm will be slow, compiled is much faster:
f = Compile[{{ll, _Integer}, {n, _Integer}},
Module[{l, digitcount, log10power, raised, found, firstdigits, pwr = 2},
l = Abs[ll];
digitcount = Floor[Log[10, l]];
log10power = Log[10, pwr];
raised = -1;
found = 0;
While[found < n,
raised++;
firstdigits = Floor[10^(FractionalPart[log10power raised] + digitcount)];
If[firstdigits == l,
found += 1;
]
];
Return[raised]
]
];
f[12, 1]
f[12, 2]
f[123, 45]
f[123, 12345]
f[123, 678910]
- Output:
7 80 12710 3510491 193060223
Nim
This is a translation to Nim of the very efficient Pascal alternative algorithm, with minor adjustments.
import math, strformat
const
Lfloat64 = pow(2.0, 64)
Log10_2_64 = int(Lfloat64 * log10(2.0))
#---------------------------------------------------------------------------------------------------
func ordinal(n: int): string =
case n
of 1: "1st"
of 2: "2nd"
of 3: "3rd"
else: $n & "th"
#---------------------------------------------------------------------------------------------------
proc findExp(number, countLimit: int) =
var i = number
var digits = 1
while i >= 10:
digits *= 10
i = i div 10
var lmtLower, lmtUpper: uint64
var log10num = log10((number + 1) / digits)
if log10num >= 0.5:
lmtUpper = if (number + 1) / digits < 10: uint(log10Num * (Lfloat64 * 0.5)) * 2 + uint(log10Num * 2)
else: 0
log10Num = log10(number / digits)
lmtLower = uint(log10Num * (Lfloat64 * 0.5)) * 2 + uint(log10Num * 2)
else:
lmtUpper = uint(log10Num * Lfloat64)
lmtLower = uint(log10(number / digits) * Lfloat64)
var count = 0
var frac64 = 0u64
var p = 0
if lmtUpper != 0:
while true:
inc p
inc frac64, Log10_2_64
if frac64 in lmtLower..lmtUpper:
inc count
if count >= countLimit:
break
else:
# Searching for "999...".
while true:
inc p
inc frac64, Log10_2_64
if frac64 >= lmtLower:
inc count
if count >= countLimit:
break
echo fmt"""The {ordinal(count)} occurrence of 2 raised to a power""" &
fmt""" whose product starts with "{number}" is {p}"""
#———————————————————————————————————————————————————————————————————————————————————————————————————
findExp(12, 1)
findExp(12, 2)
findExp(123, 45)
findExp(123, 12345)
findExp(123, 678910)
- Output:
Processor: Core I5 8250U
Compilation command: nim c -d:danger --passC:-flto leading12.nim
Time: about 110 ms
The 1st occurrence of 2 raised to a power whose product starts with "12" is 7 The 2nd 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 12710 The 12345th occurrence of 2 raised to a power whose product starts with "123" is 3510491 The 678910th occurrence of 2 raised to a power whose product starts with "123" is 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 :-)
program Power2FirstDigits;
uses
sysutils,
strUtils;
const
{$IFDEF FPC}
{$MODE DELPHI}
ld10 :double = ln(2)/ln(10);// thats 1/log2(10)
{$ELSE}
ld10 = 0.30102999566398119521373889472449;
function Numb2USA(const S: string): string;
var
i, NA: Integer;
begin
i := Length(S);
Result := S;
NA := 0;
while (i > 0) do
begin
if ((Length(Result) - i + 1 - NA) mod 3 = 0) and (i <> 1) then
begin
insert(',', Result, i);
inc(NA);
end;
Dec(i);
end;
end;
{$ENDIF}
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 := 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.
- 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
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.
- 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
PascalABC.NET
function p(L,n: integer): integer;
begin
var logof2 := log10(2);
var places := trunc(log10(L));
var nfound := 0;
var i := 1;
while True do
begin
var a := i * logof2;
var b := trunc(power(10,a-trunc(a)+places));
if L = b then
begin
nfound += 1;
if nfound = n then break
end;
i += 1;
end;
Result := i;
end;
begin
foreach var (L,n) in Arr((12, 1), (12, 2), (123, 45), (123, 12345), (123, 678910)) do
Println($'p({n},{L}) = {p(n, L)}')
end.
- Output:
p(1,12) = 40 p(2,12) = 58 p(45,123) = 12868 p(12345,123) = 3398841 p(678910,123) = 188197328
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);
}
- 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
with javascript_semantics 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() atom t0 = time() for i=1 to length(tests)-(2*(platform()=JS)) 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 ?elapsed(time()-t0)
- 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]
(The last two tests are simply too much for pwa/p2js)
Python
Using logs, as seen first in the Pascal example.
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))
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
Racket
First implementation is an untyped, naive revision of the Pascal algorithm. But there is a lot of casting between the exact integers an floats. As well as runtime type checking.
Then there is the typed racket version, which is stricter about the use of types (although, I'm not super happy at the algorithm counting using floating-point integers... but it's faster)
Compare and contrast...
Untyped Racket
#lang racket
(define (fract-part f)
(- f (truncate f)))
(define ln10 (log 10))
(define ln2/ln10 (/ (log 2) ln10))
(define (inexact-p-test L)
(let ((digit-shift (let loop ((L (quotient L 10)) (shift 1))
(if (zero? L) shift (loop (quotient L 10) (* 10 shift))))))
(λ (p) (= L (truncate (* digit-shift (exp (* ln10 (fract-part (* p ln2/ln10))))))))))
(define (p L n)
(let ((test? (inexact-p-test L)))
(let loop ((j 1) (n (sub1 n)))
(cond [(not (test? j)) (loop (add1 j) n)]
[(zero? n) j]
[else (loop (add1 j) (sub1 n))]))))
(module+ main
(define (report-p L n)
(time (printf "p(~a, ~a) = ~a~%" L n (p L n))))
(report-p 12 1)
(report-p 12 2)
(report-p 123 45)
(report-p 123 12345)
(report-p 123 678910))
- Output:
p(12, 1) = 7 cpu time: 1 real time: 1 gc time: 0 p(12, 2) = 80 cpu time: 0 real time: 0 gc time: 0 p(123, 45) = 12710 cpu time: 5 real time: 5 gc time: 0 p(123, 12345) = 3510491 cpu time: 439 real time: 442 gc time: 23 p(123, 678910) = 193060223 cpu time: 27268 real time: 27354 gc time: 194
Typed Racket
#lang typed/racket
(: fract-part (-> Float Float))
(: ln10 Positive-Float)
(: ln2/ln10 Positive-Float)
(: p (-> Positive-Index Positive-Index Positive-Integer))
(define (fract-part f)
(- f (truncate f)))
(define ln10 (cast (log 10) Positive-Float))
(define ln2/ln10 (cast (/ (log 2) ln10) Positive-Float))
(define (inexact-p-test [L : Positive-Index])
(let ((digit-shift : Nonnegative-Float
(let loop ((L (quotient L 10)) (shift : Nonnegative-Float 1.))
(if (zero? L) shift (loop (quotient L 10) (* 10. shift)))))
(l (exact->inexact L)))
(: f (-> Nonnegative-Float Boolean))
(define (f p) (= l (truncate (* digit-shift (exp (* ln10 (fract-part (* p ln2/ln10))))))))
f))
(define (p L n)
(let ((test? (inexact-p-test L)))
(let loop : Positive-Integer ((j : Positive-Float 1.) (n : Index (sub1 n)))
(cond [(not (test? j)) (loop (add1 j) n)]
[(zero? n) (assert (exact-round j) positive?)]
[else (loop (add1 j) (sub1 n))]))))
(module+ main
(: report-p (-> Positive-Index Positive-Index Void))
(define (report-p L n)
(time (printf "p(~a, ~a) = ~a~%" L n (p L n))))
(report-p 12 1)
(report-p 12 2)
(report-p 123 45)
(report-p 123 12345)
(report-p 123 678910))
- Output:
p(12, 1) = 7 cpu time: 1 real time: 1 gc time: 0 p(12, 2) = 80 cpu time: 0 real time: 0 gc time: 0 p(123, 45) = 12710 cpu time: 5 real time: 5 gc time: 0 p(123, 12345) = 3510491 cpu time: 237 real time: 231 gc time: 31 p(123, 678910) = 193060223 cpu time: 10761 real time: 10794 gc time: 17
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.
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);
}
- 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
/*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))
- 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.
RPL
The 6 RND
sequence is necessary on calculators, which do the math in simple precision. It can be removed when executing the program on a double precision emulator.
« SWAP DUP XPON ALOG 2 LOG → digits factor log2
« 0
WHILE OVER 0 > REPEAT
1 +
DUP log2 * FP ALOG 6 RND factor * IP
IF digits == THEN SWAP 1 - SWAP END
END
SWAP DROP
» » 'P' STO
12 1 P 12 2 P 123 45 P
- Output:
3: 7 2: 80 1: 12710
The last result needs 29 minutes on a basic HP-48SX.
Ruby
def p(l, n)
test = 0
logv = Math.log(2.0) / Math.log(10.0)
factor = 1
loopv = l
while loopv > 10 do
factor = factor * 10
loopv = loopv / 10
end
while n > 0 do
test = test + 1
val = (factor * (10.0 ** ((test * logv).modulo(1.0)))).floor
if val == l then
n = n - 1
end
end
return test
end
def runTest(l, n)
print "P(%d, %d) = %d\n" % [l, n, p(l, n)]
end
runTest(12, 1)
runTest(12, 2)
runTest(123, 45)
runTest(123, 12345)
runTest(123, 678910)
- Output:
P(12, 1) = 7 P(12, 2) = 80 P(123, 45) = 12710 P(123, 12345) = 3510491 P(123, 678910) = 193060223
Rust
fn power_of_two(l: isize, n: isize) -> isize {
let mut test: isize = 0;
let log: f64 = 2.0_f64.ln() / 10.0_f64.ln();
let mut factor: isize = 1;
let mut looop = l;
let mut nn = n;
while looop > 10 {
factor *= 10;
looop /= 10;
}
while nn > 0 {
test = test + 1;
let val: isize = (factor as f64 * 10.0_f64.powf(test as f64 * log % 1.0)) as isize;
if val == l {
nn = nn - 1;
}
}
test
}
fn run_test(l: isize, n: isize) {
println!("p({}, {}) = {}", l, n, power_of_two(l, n));
}
fn main() {
run_test(12, 1);
run_test(12, 2);
run_test(123, 45);
run_test(123, 12345);
run_test(123, 678910);
}
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
Scala
object FirstPowerOfTwo {
def p(l: Int, n: Int): Int = {
var n2 = n
var test = 0
val log = math.log(2) / math.log(10)
var factor = 1
var loop = l
while (loop > 10) {
factor *= 10
loop /= 10
}
while (n2 > 0) {
test += 1
val value = (factor * math.pow(10, test * log % 1)).asInstanceOf[Int]
if (value == l) {
n2 -= 1
}
}
test
}
def runTest(l: Int, n: Int): Unit = {
printf("p(%d, %d) = %,d%n", l, n, p(l, n))
}
def main(args: Array[String]): Unit = {
runTest(12, 1)
runTest(12, 2)
runTest(123, 45)
runTest(123, 12345)
runTest(123, 678910)
}
}
- 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
Sidef
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)}"
}
- 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
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))")
}
- Output:
p(12, 1) = 7 p(12, 2) = 80 p(123, 45) = 12710 p(123, 12345) = 3510491 p(123, 678910) = 193060223
Faster Version
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))")
}
- Output:
Same as before.
Visual Basic .NET
Module Module1
Function Func(ByVal l As Integer, ByVal n As Integer) As Long
Dim res As Long = 0, f As Long = 1
Dim lf As Double = Math.Log10(2)
Dim i As Integer = l
While i > 10
f *= 10
i /= 10
End While
While n > 0
res += 1
If CInt((f * Math.Pow(10, res * lf Mod 1))) = l Then
n -= 1
End If
End While
Return res
End Function
Sub Main()
Dim values = {Tuple.Create(12, 1), Tuple.Create(12, 2), Tuple.Create(123, 45), Tuple.Create(123, 12345), Tuple.Create(123, 678910), Tuple.Create(99, 1)}
For Each pair In values
Console.WriteLine("p({0,3}, {1,6}) = {2,11:n0}", pair.Item1, pair.Item2, Func(pair.Item1, pair.Item2))
Next
End Sub
End Module
- Output:
p( 12, 1) = 60 p( 12, 2) = 70 p(123, 45) = 12,710 p(123, 12345) = 3,496,509 p(123, 678910) = 192,278,374 p( 99, 1) = 93
Wren
Just the first version which has turned out to be much quicker than the Go entry (around 28 seconds on the same machine). Frankly, I've no idea why.
import "./fmt" for Fmt
import "./math" for Math
var ld10 = Math.ln2 / Math.ln10
var p = Fn.new { |L, n|
var i = L
var digits = 1
while (i >= 10) {
digits = digits * 10
i = (i/10).floor
}
var count = 0
i = 0
while (count < n) {
var e = (Math.ln10 * (i * ld10).fraction).exp
if ((e * digits).truncate == L) count = count + 1
i = i + 1
}
return i - 1
}
var start = System.clock
var params = [ [12, 1] , [12, 2], [123, 45], [123, 12345], [123, 678910] ]
for (param in params) {
Fmt.print("p($d, $d) = $,d", param[0], param[1], p.call(param[0], param[1]))
}
System.print("\nTook %(System.clock - start) seconds.")
- 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 16.51308 seconds.
Yabasic
FAC = 0.30102999566398119521373889472449302677
print p(12, 1)
print p(12, 2)
print p(123, 45)
print p(123, 12345)
print p(123, 678910)
end
sub p(L, n)
cont = 0 : j = 0
LS$ = str$(L)
while cont < n
j = j + 1
x = FAC * j
//if x < len(LS$) continue while 'sino da error
y = 10^(x-int(x))
y = y * 10^len(LS$)
digits$ = str$(y)
if left$(digits$, len(LS$)) = LS$ cont = cont + 1
end while
return j
end sub
zkl
Lots of float are slow so I've restricted the tests.
// 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);
}
}
GNU Multiple Precision Arithmetic Library
GMP is just used to give some context on the size of the numbers we are dealing with.
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()));
}
- 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)
- Programming Tasks
- Solutions by Programming Task
- 11l
- ALGOL 68
- BASIC256
- C
- C++
- C sharp
- D
- Delphi
- EasyLang
- F Sharp
- Factor
- FreeBASIC
- FutureBasic
- Gambas
- Go
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Mathematica
- Wolfram Language
- Nim
- Pascal
- PascalABC.NET
- Perl
- Phix
- Phix/mpfr
- Python
- Racket
- Raku
- REXX
- RPL
- Ruby
- Rust
- Scala
- Sidef
- Swift
- Visual Basic .NET
- Wren
- Wren-fmt
- Wren-math
- Yabasic
- Zkl
- GMP