Self numbers: Difference between revisions
Content added Content deleted
(Added AppleScript.) |
(→sliding sieve: + tidy generator) |
||
Line 950: | Line 950: | ||
Memory use is pretty low, around ~4MB.<br> |
Memory use is pretty low, around ~4MB.<br> |
||
[unlike the above, this is perfectly happy on both 32 and 64 bit]<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 |
|||
Aside: the getd_index() check is often worth trying with phix dictionaries: if there is a high probability that |
|||
of previous primes. Here, you only need to eliminate digital additions of previous safe numbers. |
|||
the key already exists, it will yield a win, but with a low probability it will just be unhelpful overhead. |
|||
Only after writing this did I understand how to write a sliding sieve, which it turns out is a much better idea (see below). |
|||
<lang Phix>integer gd = new_dict(), g = 1, gdhead = 2, n = 0 |
|||
Still, this is pretty interesting and quite neat. |
|||
<lang Phix>integer gd = new_dict(), gdhead = 2, n = 0 |
|||
function ng(integer n) |
function ng(integer n) |
||
Line 965: | Line 967: | ||
function self(integer /*i*/) |
function self(integer /*i*/) |
||
-- note: assumes sequentially invoked (arg i unused) |
-- note: assumes sequentially invoked (arg i unused) |
||
integer nxt |
|||
n += 1 |
n += 1 |
||
while n=gdhead do |
while n=gdhead do |
||
gdhead = pop_dict(gd)[1] |
|||
setd(ng(gdhead),0,gd) |
|||
if getd_index(nxt, gd)=NULL then -- (~25% gain) |
|||
setd(nxt,0,gd) |
|||
end if |
|||
g += 1 |
|||
end while |
|||
integer wasgdhead = gdhead |
|||
while true do |
|||
gdhead = pop_dict(gd)[1] |
|||
if gdhead!=wasgdhead then exit end if |
|||
-- ?{"ding",wasgdhead} -- 2, once only... |
|||
end while |
|||
nxt = ng(gdhead) |
|||
-- if getd_index(nxt, gd)=NULL then -- (~1% loss) |
|||
setd(nxt,0,gd) |
|||
-- end if |
|||
n += (n!=gdhead) |
n += (n!=gdhead) |
||
end while |
end while |
||
setd(ng(n),0,gd) |
|||
return n |
return n |
||
end function |
end function |
||
Line 1,023: | Line 1,010: | ||
</pre> |
</pre> |
||
For the record, I would not be at all surprised should a translation of this beat 20 minutes (for 1e8) |
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}}== |
=={{header|REXX}}== |