Jump to content

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

First power of 2 that has leading decimal digits of 12 (view source)

Revision as of 21:05, 15 January 2020

1,942 bytes removed ,  4 years ago
→‎{{header|Go}}: Replaced previous solution with an infinitely better Pascal translation.
m (→‎{{header|Pascal}}: removed part after end.)
(→‎{{header|Go}}: Replaced previous solution with an infinitely better Pascal translation.)
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/gmpmath"
"strconvtime"
"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 uintuint64) string {
s := fmt.Sprintf("%d", n)
le := len(s)
Line 120 ⟶ 55:
}
return s
▲}
 
▲func p(L, n intuint64) uintuint64 {
▲ i := big.NewInt(1)L
▲ onedigits := big.NewIntuint64(1)
▲ for i >= 10 {
▲ switchdigits shift*= {10
▲ poweri +/= shift10
▲ }
▲ count := uint64(0)
▲ for counti := 0; count < n; counti++ {
e := math.Exp(math.Ln10 * math.Mod(float64(i)*ld10, 1))
if uint64(math.Trunc(e*float64(digits))) == L {
▲ count++ shift = 485
▲ case 90:}
▲ }
▲ return poweri - 1
}
 
func main() {
start := time.Now()
params := [][2]intuint64{{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 ⟶ 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>
PureFox
9,490

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/297454"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information