First power of 2 that has leading decimal digits of 12: Difference between revisions

Content added Content deleted

Inline

@@ Line 37: / Line 37: @@
 =={{header|Go}}==
+{{trans|Pascal}}
-{{libheader|GMP(Go wrapper)}}
-<br>
-A (more or less) brute force approach suffices for the first 3 parts of this task but a much quicker method is needed for the other two parts.
-Based on some prior analysis I did, the first three powers of two to begin with "123" are: 2^90, 2^379 and 2^575. Notice that the respective difference in powers is 90, 289 and 196.
-For higher powers, after a 196 difference, I found that the next difference in powers was either 289 or 485 (= 289 + 196), that 289 was always followed by a difference of 196 and that 485 was followed by either 196 or 485 again.
-However, the numbers are so large here that (even using GMP) p(123, 12345) is still taking about 4.5 minutes to compute on my Core i7 and, judging by the REXX solution, p(123, 678910) would take well in excess of 4 hours.
-:::: <small> The REXX solution (on a 3.2GHz processor) took 275 seconds. &nbsp; 2<sup>193,060,223</sup> has over 158 million digits. &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:16, 15 January 2020 (UTC) (this msg to be removed later?)</small>
-I have therefore just completed the first 4 parts for now.
 <lang go>package main
 import (
     "fmt"
-    big "github.com/ncw/gmp"
+    "math"
-    "strconv"
+    "time"
-    "strings"
 )
+var ld10 = math.Ln2 / math.Ln10
-func p123(n int) uint {
-    power, shift := uint(0), uint(90)
-    one := big.NewInt(1)
-    temp := new(big.Int)
-    for count := 0; count < n; count++ {
-        power += shift
-        switch shift {
-        case 90:
-            shift = 289
-        case 289:
-            shift = 196
-        case 196:
-            shift = 289
-            temp.Set(one)
-            temp.Lsh(temp, power+289)
-            if !strings.HasPrefix(temp.String(), "123") {
-                shift = 485
-            }
-        case 485:
-            shift = 196
-            temp.Set(one)
-            temp.Lsh(temp, power+196)
-            if !strings.HasPrefix(temp.String(), "123") {
-                shift = 485
-            }
-        }
-    }
-    return power
-}
-func p(L, n int) uint {
-    prefix := strconv.Itoa(L)
-    if prefix == "123" {
-        return p123(n)
-    }
-    count := 0
-    power, shift := uint(1), uint(1)
-    i := big.NewInt(1)
-    for {
-        i := i.Lsh(i, shift)
-        if strings.HasPrefix(i.String(), prefix) {
-            count++
-            if count == n {
-                break
-            }
-            shift = 4 // next number is going to be more than 8 times as big
-        } else {
-            shift = 1
-        }
-        power += shift
-    }
-    return power
-}
-func commatize(n uint) string {
+func commatize(n uint64) string {
     s := fmt.Sprintf("%d", n)
     le := len(s)
@@ Line 120: / Line 55: @@
     }
     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]int{{12, 1}, {12, 2}, {123, 45}, {123, 12345},} // {123, 678910} }
+    params := [][2]uint64{{12, 1}, {12, 2}, {123, 45}, {123, 12345}, {123, 678910}}
     for _, param := range params {
         fmt.Printf("p(%d, %d) = %s\n", param[0], param[1], commatize(p(param[0], param[1])))
     }
+    fmt.Printf("\nTook %s\n", time.Since(start))
 }</lang>
@@ Line 135: / Line 89: @@
 p(123, 45) = 12,710
 p(123, 12345) = 3,510,491
+p(123, 678910) = 193,060,223
+Took 38.015225244s
 </pre>
 =={{header|Pascal}}==
 First convert 2**i -> 10**x => x= ln(2)/ln(10) *i<BR>