Talk:First power of 2 that has leading decimal digits of 12: Difference between revisions
Content added Content deleted
(→is there an easy way to get those delta 2^i (delta = i-Last_i ) ?: Added some comments.) |
|||
Line 25: | 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> |
<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)~ |
--[[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) |