Author |
Topic: Finding first n Ramanujan numbers efficiently (Read 5878 times) |
|
eenampicchi
Newbie
Posts: 10
|
 |
Finding first n Ramanujan numbers efficiently
« on: Oct 27th, 2010, 8:14am » |
 Quote  Modify
|
Ramanujan numbers are those numbers x such that there are four other numbers a,b,c,d that satisfy the property a^3 + b^3 = c^3 + d^3 = x. That is, they should be expressibly as the sum of cubes of two distinct sets of numbers. Given a number N, write an algorithm to print all the Ramanujan numbers from 1 to N. N can be very very large, so efficiency is key here.
I have an O(n^3) algorithm, but I think it needs to get better than that. My proposed algorithm :
1) Generate all cubes from 1 to N^(1/3) and keep in a sorted order.
2) For each pair of numbers in this list, find the sum, and search for another pair of numbers which add up to the same.
Generating all pairs can be done in O(n^2) time, and finding a pair that sums to a particular value can be done in O(n) time. (There is a thread in this forum for this problem).
How can I improve this?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding first n Ramanujan numbers efficiently
« Reply #1 on: Oct 27th, 2010, 8:52am » |
Quote Modify
|
I would think you could simply for each number K, run through all cubes C smaller or equal to half the number, then see if K-C is a cube (e.g. take the cuberoot, round, and cube). If you find exactly two such C, then K is a Ramanujan number.
I think this should be O(N4/3).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding first n Ramanujan numbers efficiently
« Reply #2 on: Oct 27th, 2010, 8:57am » |
Quote Modify
|
Actually, with some modifications, your algorithm would be better (if you have sufficient memory).
Generate the O(N1/3) cubes, find the sum of each (unordered) pair O(N2/3), use a hash to count how often each sum occurs, and return the ones that occurred twice.
So O(N2/3) total. But it may take O(N2/3) space as well.
There's probably room for improvement though.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Finding first n Ramanujan numbers efficiently
« Reply #3 on: Oct 28th, 2010, 10:16am » |
Quote Modify
|
on Oct 27th, 2010, 8:14am, eenampicchi wrote:Ramanujan numbers are those numbers x such that there are four other numbers a,b,c,d that satisfy the property a^3 + b^3 = c^3 + d^3 = x. That is, they should be expressibly as the sum of cubes of two distinct sets of numbers. Given a number N, write an algorithm to print all the Ramanujan numbers from 1 to N. N can be very very large, so efficiency is key here.
I have an O(n^3) algorithm, but I think it needs to get better than that. My proposed algorithm :
1) Generate all cubes from 1 to N^(1/3) and keep in a sorted order.
2) For each pair of numbers in this list, find the sum, and search for another pair of numbers which add up to the same.
Generating all pairs can be done in O(n^2) time, and finding a pair that sums to a particular value can be done in O(n) time. (There is a thread in this forum for this problem).
How can I improve this? |
|
Your algorithm is not that bad, you are calculating the order in wrong way. For a given n, finding all the cubes <= n is actually O(n1/3).
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
eenampicchi
Newbie
Posts: 10
|
|
Re: Finding first n Ramanujan numbers efficiently
« Reply #4 on: Oct 28th, 2010, 6:59pm » |
Quote Modify
|
I think towr had the orders precise. My notation was confusing, I should have mentioned that I was using n = N^1/3.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print