Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[JoshuaFH]

I've gotten into Helldivers 2. It has these things called stratagems which are air strikes and stuff you can call down. To do that you need to input a combination of up, down, left, and right. There are something like 20 or 30 stratagems in the game, but it occurred to me that the devs have a serious developmental problem: there's only so many unique combinations you can have without any of them overlapping. The stratagems cannot overlap, or players won't be able to bring both at the same time. It seems like a math problem, but I have no clue how I'd even get started on it, and considering my post on the Helldivers 2 Reddit got instantly deleted for being a "trivial question" I'm not sure who else I'd bring the question to but here.

Not important, just really curious.

[bloop_bleep]

If you have no limit on how many inputs are required for a strategem you can make it so you never run out of combinations. If you have a limited number of inputs you can figure out the maximum number of unique combinations: it's 4 to the power of the number of inputs.

By the way, a correspondence between combinations of characters and items you want to convey such that no combination is a prefix of another is called a Huffman encoding. There is a way to make such an assignment based on how often you use each item to minimize the average number of characters used to describe items.

[Ulfarr]

The closest analog I can think are the codons (genetic code) where you have four "bases" A, G, C, U (for dna) and they are combined in groups of 3, resulting in 64 different combinations (4^3 = 64).

In a similar vein if the helldivers startegems use groups of four then there are already 4^4=256 different combinations. I guess that should be more than enough for the entire game.

[JoshuaFH]

If you have no limit on how many inputs are required for a strategem you can make it so you never run out of combinations. If you have a limited number of inputs you can figure out the maximum number of unique combinations: it's 4 to the power of the number of inputs.

By the way, a correspondence between combinations of characters and items you want to convey such that no combination is a prefix of another is called a Huffman encoding. There is a way to make such an assignment based on how often you use each item to minimize the average number of characters used to describe items.

There is a limit. (Sorry to get back to this so much later). For most stratagems, that's 6. And the minimum seems to be 3. I'm not sure how to go about this huffman encoding, but googling it, it seems to be a method of compression?

[da_nang]

Not really help, just a curiosity. At first I thought it was just a coincidence, but now I've nerd-sniped myself.

How many square-free integers a>1 exist such that the cube of a, and the squares nearest to that cube, are separated by the square roots of the other squares?

By that I mean, is there a natural number b such that a³ - b² = b+1 and (b+1)² - a³ = b, or alternatively, a³ - (b+1)² = b and b² - a³ = (b+1)? Let's call the first set of conditions H, and the alternative set of conditions G.

All I've been able to deduce is that H implies 4a³-3 must be a square number, and G is impossible since it implies b = (√(4a³+5)+1)/2 and b = (√(4a³+5)-3)/2, which results in 1/2 = -3/2.

Other than that, 7 is the only one of the square-free integers from the list on OIES that satisfies H (7³ - 18² = 19 and 19²-7³ = 18). In fact, I've checked all square-free integers below ten million with some Python code, and 7 is the only one of those that satisfies H.

Considering the problem and the necessary conditions are so simple, I'm surprised there are no other examples. Am I too blind to see something obvious?

[Magmacube_tr]

What is 6 x 3?

[zhijinghaofromchina]

根据乘法表口诀，三六一十八， so， I guess 3*6=18

[NJW2000]

By that I mean, is there a natural number b such that a³ - b² = b+1 and (b+1)² - a³ = b, or alternatively, a³ - (b+1)² = b and b² - a³ = (b+1)? Let's call the first set of conditions H, and the alternative set of conditions G.

Very interesting question. I'd like to see the python code too, mine was rubbish and chugged the laptop hard when checking a up to 10,000.

Had a look at this but haven't made much progress on the why of it. I'm not a number theorist though. Here's a few things:

Facts about squares tell us that the first part of H is enough, i.e. a^3 = b^2 + b + 1 means that a^3 + b is (b+1)^2.

Wolfram gave me 4 integer solutions for a^3 - b^2 - b - 1 = 0 , but the other 3 rely on negative or 0 a or b.

I think you can just reformulate the problem as: 4 a^3 = k^2 +3 for some integers a,k, but I don't know why that only has the 4 integer solutions.


You're right that G is impossible for positive integer a and b. There's a nice way of seeing why:

suppose G holds for some integer a, b

Then a^3 = b (b+1)

b and b+1 share no common factors... so must be cubes of integers themselves, as otherwise a would not be a cube.

The only integer cubes with a difference of 1 are -1, 0 and 1. So we obtain b=0 or b+1 = 0, so a=0 and b=-1 or b=0

Would love to see other people chime in on this, but I'd advise you to check if it's a case of an unsolved problem in number theory before getting too invested. There's a lot of those, and some can be stated very simply.

[da_nang]

My python script for checking the numbers is below. It checks all square-free numbers below ten million in a few minutes. Checking all square free numbers below one hundred million would take hours. My computer is unable to check for all square-free numbers below one billion due to a lack of memory. I believe the sieve algorithm is the cause. An iterative brute-force method would be much slower but shouldn't have memory issues.

Code: (SquareFreeCube.py) [Select]

#Generator to find square-free numbers using sieve
#By Graipher
#https://codereview.stackexchange.com/questions/151949/square-free-number

def square_free_sieve(limit):
    """Generator that yields all square free numbers less than limit"""
    a = [True] * limit
    # Needed so we don't mark off multiples of 1^2
    yield 1
    a[0] = a[1] = False
    for i, is_square_free in enumerate(a):
        if is_square_free:
            yield i
            i2 = i * i
            for n in range(i2, limit, i2):
                a[n] = False

#Newton's method for "integer" square root, using integer arithmetic
#Used because math.sqrt is inaccurate for large integers
#Should produce floor(sqrt(n))
#By user448810 et al.
#https://stackoverflow.com/questions/15390807/integer-square-root-in-python

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def squareFreeCube(limit):
    """Generates a list of all square-free numbers a > 1 below limit
    that satisfies a^3 - b^2 = b+1 and (b+1)^2 - a^3 = b for some
    natural number b.
    """
    #Generate all square-free numbers below limit, excluding 1.
    squareFreeNumbers = list(square_free_sieve(limit))[1::]

    output = []

    for a in squareFreeNumbers:
        discriminant = 4*a**3 - 3

        #Discriminant 4a^3-3 must be a square number
        root = isqrt(discriminant) #equivalent to floor(sqrt(discriminant))
        if root**2 != discriminant:
            continue

        #print "{} passes discriminant test".format(a)

        #Calculate natural number b from b^2 + b + 1 - a^3 = 0
        b = (root-1)/2

        #print "b = {}".format(b)

        #First condition should be automatically satisfied
        if a**3 - b**2 != b + 1:
            continue

        #print "{} passes first condition".format(a)

        #Second condition
        if (b+1)**2 - a**3 != b:
            continue

        #print "{} passes second condition".format(a)

        output.append(a)

    return output

maxNumber = 10000000

for n in squareFreeCube(maxNumber):
    print n

I've given it some thought, though.

I at first thought it may be related to Fermat's last theorem (probably because of old an Numberphile or Mathologer video), and one conjecture that caught my eye was the Fermat-Catalan conjecture. Unfortunately, the sum of the reciprocals of the exponents in H is greater than one.

There's also the Beal conjecture, but that doesn't apply here because two of the terms are linear or quadratic.

Another thought: if 4a³-3 = k² for some natural number k is sufficient (only 7 passed the discriminant test in the script), then that is similar to an elliptic curve. I'm not the most familiar with them, but some google-fu seems to suggest elliptic curves have a finite number of integral points. Unfortunately, the cube coefficient 4 throws a spanner into the mix. Sure, I could substitute a = u/4^1/3 to get the proper elliptic curve form, but now an integral point in (k,u) necessarily means a is irrational.

EDIT: On reflection, I can substitute k = 2v, which gives me 4a³-3 = 4v² <=> a³-3/4 = v², which is a proper elliptic curve, but it would require either an even k or non-integer rational v. Since k necessarily must be odd in order for b to be a natural number (cf. the formula for the roots of the original quadratic in H), v must therefore be a non-integer rational.

That did, however, lead me to Siegel's theorem on integral points and Falting's theorem, but they're a bit outside my field of expertise. One of those ought to tell us if the number of integer solutions are finite or infinite.

I'll take a stab at Falting's theorem. Take the curve 4a³-3-k² = 0 (for now, assume the variables are real numbers). It has the real number solutions k = +-sqrt(4a³-3), where a >= (3/4)^1/3. First, we want to check if there are any singular points. According to WolframAlpha, "a point (a,b) on a curve f(x,y)=0 is singular if the x and y partial derivatives of f are both zero at the point (a,b)."

Let f(x,y) = 4x³-3-y², and let the algebraic curve be f(x,y)=0. The partial derivatives are ∂f/∂x = 12x², and ∂f/∂y = -2y. The partial derivatives are both zero only at (0,0), which is not on the curve. Therefore, f is non-singular.

Falting's theorem therefore applies.

Now the only big question is, what is the genus of f over the rationals? Genus is roughly the number of "holes" in a topological surface, and a WolframAlpha plot seems to hint to there being zero holes, which implies infinitely many integer solutions to H, given we already know one. But I don't think eyeballing it is proof of it.

The curve is irreducible. Therefore, per Wikipedia, the genus g is given by the genus-degree formula: g = (d-1)(d-2)/2, where d is the degree. There is some discussion on the difference between arithmetic genus and geometric genus, but since the curve is non-singular then these are actually equal.

The curve has a degree of 3. Therefore, the genus must be 1. Proof: g = (d-1)(d-2)/2 = (3-1)(3-2)/2 = 2/2 = 1.

Per Falting's theorem then (assuming working with the reals didn't change anything), and since we know (7,37) is an integral point on f, the curve is an elliptic curve (apparently the cube coefficient doesn't change anything?), and the rational points form a finitely generated abelian group. Let's call this group A.

What this means is that there exists a finite number of elements x_i in A such that every element x in A can be written as a weighted sum of x_i, where the weights are integers. This does not necessarily mean that the number of elements in A is finite, however, since addition over the integers form a finitely generated abelian group, which has an infinite number elements.

Thus I'm not sure if Falting's theorem answered the central question.

Moving over to Siegel's theorem, however, we might have better luck. According to Siegel's theorem, "a smooth algebraic curve C of genus g defined over a number field K, presented in affine space in a given coordinate system, [has] only finitely many points on C with coordinates in the ring of integers O of K, provided g > 0."

Well, a smooth algebraic curve appears to be identical to a non-singular curve, according to Wikipedia, and the curve is non-singular. So f must be smooth. The rationals are a number field, and I assume a curve that is smooth over the reals is also smooth over the rationals. The curve is presented in an affine space in a given coordinate system. Finally, the genus is one which is greater than zero. Therefore, the curve has only finitely many points in the ring of integers of the number field of the rationals.

In summary then, per Siegel's theorem (if my math checks out), and assuming 4a³-3 being a square number is a sufficient condition, then there are only finitely many integral points on the curve f, and therefore only finitely many square-free numbers that satisfy H. I don't know how many there are, but there are at least four integer solutions to f(x,y) = 0: (7,+-37), and (1,+-1). Of these, only (7,37) is of interest.

If these are the only ones, then that would mean 7 is the only square-free number greater than one that satisfies H.

Now all I need is math professor to shoot me down. I'm betting there are glaring holes I'm too inexperienced to spot.