programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Bear Bibeault
• Jeanne Boyarsky
• paul wheaton
Sheriffs:
• Junilu Lacar
• Paul Clapham
• Knute Snortum
Saloon Keepers:
• Stephan van Hulst
• Ron McLeod
• Tim Moores
• salvin francis
• Carey Brown
Bartenders:
• Tim Holloway
• Frits Walraven
• Vijitha Kumara

# Practical Number?

Greenhorn
Posts: 2
The Wikipedia article is helpful, I think.
Use some integer factorization algorithm to factor the number you want, getting each prime factor and the exponent it has in the prime factorization.
Store the prime factors in an sorted list [p1,p2,p3,...,pj] and exponent [a1,a2,a3,...,aj].
Set an integer sigma to 1.
If the first prime factor is not 2, the number is not practical.
Then for each prime factor:
Multiply sigma by (p_i^a_i-1)/(p_i-1)
if sigma+1 is greater than the next largest prime factor, your number is not practical.
Else, increment i and continue again.
If that holds for every prime factor, then your number is indeed practical.

That method, assuming a decent factorization algorithm is used, would work better than the method described in the previous post, I think.

Marshal
Posts: 63795
209
If I see James tonight, I shall show him your algorithm and ask him to explain it.

Campbell Ritchie
Marshal
Posts: 63795
209
And welcome to JavaRanch Bob Johnsonson

Bob Johnsonson
Greenhorn
Posts: 2
I'm not sure I could explain why that works, but it just takes what Wikipedia says about the condition of how the ith prime factor is less than or equal to the sum of the divisors of the first i-1 factors (raised to their exponent)+1. Since the divisor function is multiplicative, i.e. σ(a*b)=σ(a)σ(b) if a and b are relatively prime, one doesn't need to compute the whole thing each time, you can just multiply by σ(p_i-1^a_i-1) each iteration, saving a bit of calculation.

Campbell Ritchie
Marshal
Posts: 63795
209
I am afraid James is likely to be too busy to help until about Wednesday or Thursday, but I passed a message to him yesterday.

I did say

. . .
So who said there was anything simple about this ?

You may find other algorithms simpler.

. . . and my algorithm runs in exponential complexity O(2^n) where n is the number of factors < m, so finding an algorithm which is less efficient than mine is quite an achievement I got it to work, however, in 20-something lines of code. When I tried 1536, however, which has 19 factors < 1536, it had >500000 combinations to search and it took about one-third second longer to print a result than smaller numbers.

 Don't destroy the earth! That's where I keep all my stuff! Including this tiny ad: global solutions you can do in your home or backyard https://coderanch.com/t/708587/global-solutions-home-backyard