Talk:First power of 2 that has leading decimal digits of 12: Difference between revisions
Talk:First power of 2 that has leading decimal digits of 12 (view source)
Revision as of 14:47, 20 January 2020
, 4 years ago→is there an easy way to get those delta 2^i (delta = i-Last_i ) ?: Added some comments.
(→is there an easy way to get those delta 2^i (delta = i-Last_i ) ?: Added some comments.) |
|||
Line 25:
<pre> 779 485 485 1651 485 485 1166 485 485 1166 485 485 1166 485 485 1166 485 485 1166 485 485 1166 485 485 1651 </pre>
--[[User Horst.h|Horst.h]]12:14, 20 January 2020 (UTC)~
:In my first (abortive) attempt at this I'd noticed that (for a prefix of "123"), after an initial {90, 289} pair, subsequent differences were either 196, 289 or 485 (= 289 + 196). Moreover, 289 was always followed by 196 but 196 could be followed by either 289 or 485, and 485 could be followed by either 196 or 485 again. I wasn't able to discern any deeper pattern than this. So I'd ended up with this (Go) code:
:<lang go>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
}</lang>
:But, it turned out that this was very slow (4.5 minutes) as opposed to your log based approach at around 40 seconds or so. In his Perl 6 solution, I notice that Thundergnat has managed to combine your log approach with searching for patterns in the differences:
:<lang perl 6>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;
}</lang>
:though, given the substantial speed-up you've already achieved with your 'alternative' version, I don't know whether considering patterns as well is going to give a worthwhile improvement. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 14:47, 20 January 2020 (UTC)
| |||