First power of 2 that has leading decimal digits of 12

(This task is taken from a   Project Euler   problem.)

Task
First power of 2 that has leading decimal digits of 12
You are encouraged to solve this task according to the task description, using any language you may know.

(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.



11lEdit

Translation of: Python
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 68Edit

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

BASIC256Edit

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.

CEdit

Translation of: Java
#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++Edit

Translation of: Java
Translation of: Go
Translation of: Pascal
// 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
C++ (clang) or C++ (gcc), compiler flags: -O3 -std=c++17
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#Edit

Translation of: 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

DEdit

Translation of: C
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

DelphiEdit

See Pascal.

F#Edit

// 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

FactorEdit

A translation of the first Pascal example:

Translation of: Pascal
Works with: Factor version 0.99 2019-10-06
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

FreeBASICEdit

#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

GoEdit

Translation of: Pascal
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

HaskellEdit

Translation of: Python
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

JEdit

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

JavaEdit

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

jqEdit

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.

JuliaEdit

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 versionEdit

Translation of: Go
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)

KotlinEdit

Translation of: Java
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 LanguageEdit

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

NimEdit

Translation of: Pascal

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

PascalEdit

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

alternativeEdit


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

PerlEdit

Translation of: Raku
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

PhixEdit

Library: Phix/mpfr
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)

PythonEdit

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

RacketEdit

Translation of: 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 RacketEdit

#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 RacketEdit

#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

RakuEdit

(formerly Perl 6)

Works with: Rakudo version 2019.11

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

REXXEdit

/*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.

RubyEdit

Translation of: C
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

RustEdit

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

ScalaEdit

Translation of: Java
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

SidefEdit

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

SwiftEdit

Translation of: Go

Slower VersionEdit

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 VersionEdit

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 .NETEdit

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

WrenEdit

Translation of: Go
Library: Wren-fmt
Library: 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.

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.

YabasicEdit

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

zklEdit

Translation of: Pascal

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);
   }
}
Library: GMP
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)