Member Avatar for MCMLXXXVIII

we are given a problem to make this in a program but i don't quite understand what it means or requires.

• Look for positive integers that are not the sum of the cubes of nine different positive integers.

can someone help me out..
Thanks

  • 3 Contributors
  • 2 Replies
  • 109 Views
  • 17 Hours Discussion Span
  • Latest Post Latest Post by mrnutty

Dani AI

Generated

asked for positive integers that cannot be written as the sum of the cubes of nine different positive integers. 's quick small-case check is the right intuition (use a small test to get a lower bound). 's reminder about correct exponent notation is also useful: write powers explicitly when you implement the check.

A robust way to answer the question up to any explicit limit N is to treat it as a constrained subset-sum: choose exactly nine distinct cube-values from the list of cubes <= N and test which totals are reachable. The fastest practical method for a full range [1..N] is a bitset/dynamic-programming approach that keeps one bitset per count (0..9). Iterating over each cube and updating counts in reverse enforces distinctness without backtracking.

Example Python implementation (computes all nonrepresentable n <= N):

def nonrepresentable_up_to(N):
    M = int(N ** (1/3))
    while (M + 1) ** 3 <= N:
        M += 1
    while M ** 3 > N:
        M -= 1

    cubes = [i**3 for i in range(1, M + 1)]
    dp = [0] * 10
    dp[0] = 1  # bit 0 set: sum 0 achievable with 0 cubes

    for c in cubes:
        for k in range(8, -1, -1):
            dp[k + 1] |= dp[k] << c

    return [s for s in range(1, N + 1) if ((dp[9] >> s) & 1) == 0]

Notes and tips:

  • The reverse k-loop makes sure each cube is used at most once, so the nine cubes are distinct.
  • Memory is about O(N) bits per dp entry (ten entries). This is practical for N in the low millions on a modern machine. Time scales roughly with (number of cubes) times the cost of big-int shifts.
  • If the goal is a single target n, a depth-first search with greedy largest-first choices and pruning by lower/upper bounds is faster than the full-range DP.
  • For background on sums of powers see Waring's problem. The well-known mod-9 obstruction for three cubes is discussed at Sum of three cubes; that particular congruence constraint does not directly control the nine-cube case.

This approach gives an exact list up to any chosen bound and is a practical way to explore which integers fail to be representable by nine distinct positive cubes.

Recommended Answers

All 2 Replies

Member Avatar for Firewolf

Just an idea...

The first 9 positive integers are: 1, 2, ..., 9
Their cubes are: 1, 4, ..., 81
The sum of these cubes is: 285

285 has to excluded from the list

And so on...

Member Avatar for mrnutty

>> Their cubes are: 1, 4, ..., 81

no their cubes are 1^3, 2^3 , 3^3 ... 9^3

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.