57 lines
1.8 KiB
Text
57 lines
1.8 KiB
Text
do -- find some Chowla numbers ( Chowla n = sum of divisors of n exclusing n and 1 )
|
|
|
|
-- returns the divisor sums of [1 n], the sums exclude 1 and n
|
|
local function sumDivisors( n : number ) : table
|
|
local sums <const> = {}
|
|
for i = 1, n do sums[ i ] = 0 end
|
|
for i = 2, n do
|
|
for j = i + i, n, i do sums[ j ] += i end
|
|
end
|
|
return sums
|
|
end
|
|
|
|
local ds <const> = sumDivisors( 10_000_000 )
|
|
|
|
local function chowla( n : number ) : number -- returns the Chowla number of n
|
|
local sum = 0
|
|
if n > 0 then
|
|
if n <= # ds then
|
|
sum = ds[ n ]
|
|
else
|
|
for i = 2, math.floor( math.sqrt( n ) ) do
|
|
if n % i == 0 then
|
|
local j <const> = n // i
|
|
sum += i + if i == j then 0 else j end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
return sum
|
|
end
|
|
|
|
-- first 37 chowla numbers
|
|
for n = 1, 37 do print( $"chowla({n}) = {chowla(n)}" ) end
|
|
|
|
-- number of primes up to 10_000_000
|
|
local count, power = 0, 100
|
|
for n = 2, 10_000_000 do
|
|
if chowla( n ) == 0 then count += 1 end
|
|
if n % power == 0 then
|
|
print( string.format( "There are %6d primes < %d", count, power ) )
|
|
power *= 10
|
|
end
|
|
end
|
|
|
|
-- perfect numbers to 35_000_000
|
|
local perfectMax <const> = 35_000_000
|
|
count = 0
|
|
local k, kk, p = 2, 3, 6 -- p is k * kk
|
|
while p <= perfectMax do
|
|
if chowla( p ) == p - 1 then
|
|
print( string.format( " %8d is a perfect number", p ) )
|
|
count += 1
|
|
end
|
|
k = kk + 1; kk += k; p = k * kk
|
|
end
|
|
print( $"There are {count} perfect numbers < {perfectMax}" )
|
|
end
|