Chowla numbers: Difference between revisions
→{{header|Phix}}
Line 1,037:
33,550,336
</pre>
=={{header|Phix}}==
<lang Phix>function chowla(atom n)
return sum(factors(n))
end function
function sieve(integer limit)
-- True denotes composite, false denotes prime.
-- Only interested in odd numbers >= 3
sequence c = repeat(false,limit)
for i=3 to floor(limit/3) by 2 do
-- if not c[i] and chowla(i)==0 then
if not c[i] then -- (see note below)
for j=3*i to limit by 2*i do
c[j] = true
end for
end if
end for
return c
end function
atom limit = 1e7, count = 1, pow10 = 100, t0 = time()
sequence s = {}
for i=1 to 37 do
s &= chowla(i)
end for
printf(1,"chowla[1..37]: %v\n",{s})
s = sieve(limit)
for i=3 to limit by 2 do
if not s[i] then count += 1 end if
if i==pow10-1 then
printf(1,"Count of primes up to %,d = %,d\n", {pow10, count})
pow10 *= 10
end if
end for
count = 0
--limit = 35_000_000
limit = iff(machine_bits()=32?1.4e11:2.4e18)
--limit = power(2,iff(machine_bits()=32?53:63)) -- (see note below)
integer i=2
while true do
atom p = power(2,i-1)*(power(2,i)-1) -- perfect numbers must be of this form
if p>limit then exit end if
if chowla(p)==p-1 then
printf(1,"%,d is a perfect number\n", p)
count += 1
end if
i += 1
end while
printf(1,"There are %d perfect numbers <= %,d\n",{count,limit})
?elapsed(time()-t0)</lang>
The use of chowla() in sieve() does not actually achieve anything other than slow it down, so I took it out.
{{out}}
<pre>
chowla[1..37]: {0,0,0,2,0,5,0,6,3,7,0,15,0,9,8,14,0,20,0,21,10,13,0,35,5,15,12,27,0,41,0,30,14,19,12,54,0}
Count of primes up to 100 = 25
Count of primes up to 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
6 is a perfect number
28 is a perfect number
496 is a perfect number
8,128 is a perfect number
33,550,336 is a perfect number
8,589,869,056 is a perfect number
137,438,691,328 is a perfect number
2,305,843,008,139,952,128 is a perfect number
There are 8 perfect numbers <= 9,223,372,036,854,775,808
</pre>
Note that 32-bit only finds the first 7 perfect numbers, but does so in 0.4s, whereas 64-bit
takes just under 45s to find the 8th one. Using the theoretical (power 2) limits, those times
become 4s and 90s respectively, without finding anything else.
=={{header|PowerBASIC}}==
| |||