Self numbers: Difference between revisions
→sliding sieve: + tidy generator
(Added AppleScript.) |
(→sliding sieve: + tidy generator) |
||
Line 950:
Memory use is pretty low, around ~4MB.<br>
[unlike the above, this is perfectly happy on both 32 and 64 bit]<br>
Long story short: this works much the same as a prime sieve, in which you only need to eliminate multiples
of previous primes. Here, you only need to eliminate digital additions of previous safe numbers.
Only after writing this did I understand how to write a sliding sieve, which it turns out is a much better idea (see below).
Still, this is pretty interesting and quite neat.
<lang Phix>integer gd = new_dict(), gdhead = 2, n = 0
function ng(integer n)
Line 965 ⟶ 967:
function self(integer /*i*/)
-- note: assumes sequentially invoked (arg i unused)
n += 1
while n=gdhead do
n += (n!=gdhead)
end while
setd(ng(n),0,gd)
return n
end function
Line 1,023 ⟶ 1,010:
</pre>
For the record, I would not be at all surprised should a translation of this beat 20 minutes (for 1e8)
=== sliding sieve ===
Mid-speed, perhaps helped by a slightly smarter way of calculating/updating the digit sums<br>
Similar to some other entries, we (only) need a sieve of 9*9, +1 here as I test an entry after the slide.
<lang Phix>
--sequence sieve = repeat(0,82), -- (~25% slower)
sequence sieve = repeat(0,8192),
digits = repeat(0,10)
integer offset = 0,
digit_sum = 0,
n = 0
procedure next_self()
while true do
n += 1
for i=length(digits) to 1 by -1 do
integer d = digits[i]
if d!=9 then
digits[i] = d+1
digit_sum += 1
exit
end if
digits[i] = 0
digit_sum -= 9
end for
integer k = n+digit_sum-offset
if k>length(sieve) then
integer j = 1
for i=n-offset to length(sieve) do
sieve[j] = sieve[i]
j += 1
end for
sieve[j..$] = 0
offset = n-1
k = digit_sum+1
end if
sieve[k] = 1
if sieve[n-offset]=0 then exit end if
end while
-- (result in n)
end procedure
constant limit = 100000000
atom t0 = time()
printf(1,"The first 50 self numbers are:\n")
integer chk = 100
for i=1 to limit do
next_self()
if i<=50 then
printf(1," %3d%s",{n,iff(mod(i,25)=0?"\n":"")})
elsif i=chk then
if chk=100 then
printf(1,"\n i n time\n")
end if
printf(1,"%,12d %,13d %s\n",{i,n,elapsed(time()-t0)})
chk *= 10
end if
end for
printf(1,"\nEstimated time for %,d :%s\n",{1e9,elapsed((time()-t0)*1e9/limit)})</lang>
{{out}}
<pre>
The first 50 self numbers are:
1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211
222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468
i n time
100 973 0.1s
1,000 10,188 0.1s
10,000 102,225 0.1s
100,000 1,022,675 0.1s
1,000,000 10,227,221 0.5s
10,000,000 102,272,662 4.5s
100,000,000 1,022,727,208 44.5s
Estimated time for 1,000,000,000 :7 minutes and 25s
</pre>
=={{header|REXX}}==
| |||