Member Avatar for ram.patil

1. .......Algorithm to find the first n Hardy-Ramanujan numbers....
since 1729 is the least .....

I request to post the solution for this............

  • 4 Contributors
  • 4 Replies
  • 2K Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by TrustyTony

Dani AI

Generated

Good call from on the definition and the naive scan. If you want the first n quickly, avoid checking every integer. Instead, generate all sums a^3+b^3 in increasing order and count how many different (a,b) pairs produce the same sum. Whenever a sum appears from exactly two distinct pairs, you have a Hardy-Ramanujan (a.k.a. taxicab) number. A min-heap lets you stream these sums without a quadratic nested loop.

import heapq

def hardy_ramanujan(n):
    # First n numbers that are sum of two positive cubes in exactly two ways.
    heap = [(1**3 + 1**3, 1, 1)]  # (sum, a, b) with a <= b
    max_a = 1
    out = []

    while len(out) < n:
        # Ensure we have seeds (a,a) for all a with 2*a^3 <= current min sum
        min_sum = heap[0][0]
        while (max_a + 1) ** 3 * 2 <= min_sum:
            max_a += 1
            heapq.heappush(heap, (max_a**3 + max_a**3, max_a, max_a))

        # Pop the smallest sum and collect all pairs producing it
        s, a, b = heapq.heappop(heap)
        heapq.heappush(heap, (a**3 + (b + 1)**3, a, b + 1))
        count = 1
        while heap and heap[0][0] == s:
            _, a2, b2 = heapq.heappop(heap)
            heapq.heappush(heap, (a2**3 + (b2 + 1)**3, a2, b2 + 1))
            count += 1

        if count == 2:   # exactly two distinct representations
            out.append(s)
    return out

Why this works: for each fixed a, the sequence a^3+a^3, a^3+(a+1)^3, … is strictly increasing. The heap always yields the global next sum; the brief seeding step guarantees we never miss smaller pairs. Using a<=b prevents counting the same pair twice. Try hardy_ramanujan(5); the first item you see will be 1729, as noted.

Recommended Answers

All 4 Replies

Member Avatar for G-Do

Hi ram.patil,

A Hardy-Ramanujan number is a number which can be expressed as the sum of two positive cubes in exactly two different ways. For example, 1729 is equal to the sum:

1^3+12^3

- or alternatively, to the sum:

9^3+10^3

- but not to any other sums of positive cubes. Let's think about a general strategy for collecting the first n of these numbers. You will need to store the numbers in an extendable data structure, such as a list. You will also need to keep trying to find numbers until you have found n of them, appending valid Hardy-Ramanujan numbers to the list as you go. To implement this, you could do a while loop which keeps looking for Hardy-Ramanujan numbers until the length of the list is n. Does that make sense?

To find the numbers themselves, you could always try the naive approach: beginning with 1729, check each number. Subtract successive integer cubes from the number and see if the difference is a cube. This could be represented by a for loop nested inside your while loop. During the for loop, keep track of every time the difference is a cube. If, when the for loop completes, the difference has been a cube only twice, you know that the number is a Hardy-Ramanujan number, and can be added to the list.

Hope this helps!

Member Avatar for ram.patil

sir , i'm very glad to hear this from u ... i tried this method and i'm successful in getting the n such numbers.

Member Avatar for tsmc

Hi,

U can find the list of Ramanujan numbers in a given range using the following program,

Good luck.

Edited by Ezzaral because: Snipped url. No promotion.
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.