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.

[McTraveller]

I think it's simpler than that, isn't it? Don't your constraints basically have

b² < a³ < (b+1)²

But you're looking for

a³ - b² = b+1
(b+1)² - a³ = b

But we have the known fact that (b+1)² - b² = 2(b+1)-1 = 2b+1
(because the squares are sums of consecutive odd numbers).

So you are looking for cubes a³ that are b+1 bigger than b².

So you are looking for cubes of the form a³ = b² + b+1

If you define c = a³ then you can solve that quadratic equation and you end up with

b = -1/2 +√(c - 3/4)

So you are looking for pairs of integers a,b that satisfy b = -1/2 + √(a³ - 3/4).

Maybe that helps...?

EDIT: fixed typo

[hops]

can someone ELI5 how/why the taylor series works?

[Maximum Spin]

I wrote this the other day, got distracted, and kind of forgot to post it, but I'll finish it up and post it now since other people are talking about it.

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?

Two adjacent squares are always separated by the sum of their roots; (x + 1)² = x² + 2x + 1, and (x² + 2x + 1) - x² = 2x + 1, which is the sum of x and x + 1. Therefore, it is sufficient that a³ = b² + b + 1 for some b.
From this it should also be clear that the second set of conditions never made sense - you're asking for a situation where (b + 1)² is equal to b² - 2b - 1 instead, which is only possible if -2b - 1 = 2b + 1, or in other words, b = -½. There are obviously no integer values compatible with this. Your quadratic analysis was wrong, though, because you're looking at the two oppositely-signed square roots; (-2 + 1)/2 and (2 - 3)/2 are perfectly possible to equate, giving that -½. You can't just subtract out the square root when it doesn't mean the same thing.

As for the 4a³-3 thing, that obviously makes (b + b + 1)², so if it's a square, it is definitely the square of two adjacent numbers that will fit the equation.

Anyway, what you're looking at is in fact an elliptic curve (substituting x for a and y for b), which are so mathematically intractable that they're used for cryptography, and you're asking for a solution as what's called a Diophantine equation, where only integer solutions are considered, which are also famously tricky to solve. So it shouldn't be too surprising that your problem is difficult.

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.

Yes, this is the core issue, you are looking for rational points on an elliptic curve. Many Diophantine equations can be reduced to this form. And yes you are allowed to make arbitrarily affine transformations on an elliptic curve function like that by exchanging variables, of course.

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.

I'm not a math professor, but I'm nevertheless confident you're not wrong about anything in particular you said here. There are indeed exactly four integer solutions, and outside those bounds the ratio of x and y is always irrational. This isn't too surprising; the successive cubes are separated by (3n² + 3n + 1) while the successive squares are of course separated by (2m + 1) as previously stated. In other words, cubes get sparser much faster than squares and are unlikely to maintain any orderly relation to them. I would suggest that, since, after all, you're looking at why a specific relationship between squares and cubes does not recur, you should be focusing your number theory on that point.

[McTraveller]

Not requesting help, as I know how to do it, but:

Nonlinear systems of equations.  Why are you so hard to get closed-form solutions!?

(Not even a differential equation in this case... just "regular"... but it's a 4-unknown system, so the bookkeeping is a hassle. Only two of the variables are nonlinear, the other two are linear. But it's still annoying.)

[da_nang]

Not requesting help, as I know how to do it, but:

Nonlinear systems of equations.  Why are you so hard to get closed-form solutions!?

(Not even a differential equation in this case... just "regular"... but it's a 4-unknown system, so the bookkeeping is a hassle. Only two of the variables are nonlinear, the other two are linear. But it's still annoying.)

Even if it's just nonlinear polynomials, powers tend to accumulate as you solve for each variable, barring clever tricks and a keen eye. That can quickly push you into quintics and beyond and poof, Abel-Ruffini. Example:

x² - x + y = 0
y² - x + 1 = 0

x² - x + y = 0 <=> x = (1 +- sqrt(1 - 4y))/2 //domain checks are an exercise for the reader

=> y² - (1 + sqrt(1 - 4y))/2 + 1 = 0 v y² - (1 - sqrt(1 - 4y))/2 + 1 = 0
<=> 2y² - 1 = sqrt(1 - 4y) v 1 - 2y² = sqrt(1 - 4y) //domain checks are an exercise for the reader
<=> (2y² - 1)² = 1 - 4y v (1 - 2y²)² = 1 - 4y
<=> 4y⁴ - 4y² + 1 = 1 - 4y
<=> 4y⁴ - 4y² + 4y = 0
<=> y⁴ - y² + y = 0
<=> y(y³ - y + 1) = 0
<=> y = 0 v y³ - y + 1 = 0

Just this simple example with quadratics pushed the polynomial degree to a quartic (factorized to a linear polynomial and a depressed cubic polynomial). Both cubics and quartics have closed-form solutions (albeit increasingly nightmarish). Eventually you'll stumble upon problems that get pushed to quintics and beyond.

By analogy, you can also look at systems of ODEs. You can repeatedly differentiate some of the equations so you can insert the other equations. As you do that, the orders of the differentiated ODEs keep growing, and the integrals become more nightmarish, if they even exist in a closed form.

[McTraveller]

In this case it involves square roots; one of the terms is of the form √(k² - y²)

So my system with variables w,x,y,z (the rest are constants)

Code: [Select]

a1 w + b1 x        + c1 √(k²-y²)        = r1
a2 w + b2 x        + c2 √(k²-y²)        = r2
       b3 √(k²-x²) + c3 y        + d3 z = r3
       b4 √(k²-x²) + c4 y        + d4 z = r4

It's just a ton of bookkeeping; it's easy to cancel terms and end up with something that looks like

Code: [Select]

A1 x        + B1 √(k²-y²) = C1
A2 √(k²-x²) + B2 y        = C2

Now I happen to know the equations actually come from some trig relations, so this system is really

Code: [Select]

A1 sin(α) + B1 cos(β) = C1
A2 cos(α) + B2 sin(β) = C2

=>
A1² A2² = (C1-B1cos(β))² A2² + (C2-B2 sin(β))² A1²
B1² B2² = (C1-A1sin(α))² B2² + (C2-A2 cos(α))² B1²

So that's a little better... I guess...  I suppose I could solve that numerically... but a closed form would be nice.