Anonymous user
Abundant, deficient and perfect number classifications: Difference between revisions
Abundant, deficient and perfect number classifications (view source)
Revision as of 21:12, 23 March 2015
, 9 years ago→{{header|Julia}}: A new entry for Julia
(→{{header|Racket}}: Much shorter code) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 286:
The sign of the difference is negative for the abundant case - where the sum is greater than the number. And we rely on order being preserved in sequences (this happens to be a fundamental property of computer memory, also).
=={{header|Julia}}==
===The Math===
A natural number can be written as a product of powers of its prime factors,
<math>
\prod_{i} p_{i}^{a_{i}}
</math>. Handily <code>Julia</code> has the <code>factor</code> function, which provides these parameters. The sum of n's divisors (n inclusive) is
<math>
\prod_{i} \frac{p_{i}^{a_{i}+1} - 1}{p_{i} - 1} = \prod_{i} p_{i}^{a_{i}} + p_{i}^{a_{i}-1} + \cdots + p_{i} + 1
</math>.
===Functions===
<code>divisorsum</code> calculates the sum of aliquot divisors. It uses <code>pcontrib</code> to calculate the contribution of each prime factor.
<lang Julia>
function pcontrib(p::Int64, a::Int64)
n = one(p)
pcon = one(p)
for i in 1:a
n *= p
pcon += n
end
return pcon
end
function divisorsum(n::Int64)
dsum = one(n)
for (p, a) in factor(n)
dsum *= pcontrib(p, a)
end
dsum -= n
end
</lang>
Perhaps <code>pcontrib</code> could be made more efficient by caching results to avoid repeated calculations.
===Main===
Use a three element array, <code>iclass</code>, rather than three separate variables to tally the classifications. Take advantage of the fact that the sign of <code>divisorsum(n) - n</code> depends upon its class to increment <code>iclass</code>. 1 is a difficult case, it is deficient by convention, so I manually add its contribution and start the accumulation with 2. All primes are deficient, so I test for those and tally accordingly, bypassing <code>divisorsum</code>.
<lang Julia>
const L = 2*10^4
iclasslabel = ["Deficient", "Perfect", "Abundant"]
iclass = zeros(Int64, 3)
iclass[1] = one(Int64) #by convention 1 is deficient
for n in 2:L
if isprime(n)
iclass[1] += 1
else
iclass[sign(divisorsum(n)-n)+2] += 1
end
end
println("Classification of integers from 1 to ", L)
for i in 1:3
println(" ", iclasslabel[i], ", ", iclass[i])
end
</lang>
===Output===
<code>
Classification of integers from 1 to 20000
Deficient, 15043
Perfect, 4
Abundant, 4953
</code>
=={{header|jq}}==
| |||