Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 171 172 [173]

Author Topic: Mathematics Help Thread  (Read 201049 times)

JoshuaFH

  • Bay Watcher
    • View Profile
Re: Mathematics Help Thread
« Reply #2580 on: April 04, 2024, 06:10:41 pm »

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.
Logged

bloop_bleep

  • Bay Watcher
    • View Profile
Re: Mathematics Help Thread
« Reply #2581 on: April 04, 2024, 06:19:46 pm »

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.
« Last Edit: April 04, 2024, 06:28:42 pm by bloop_bleep »
Logged
Quote from: KittyTac
The closest thing Bay12 has to a flamewar is an argument over philosophy that slowly transitioned to an argument about quantum mechanics.
Quote from: thefriendlyhacker
The trick is to only make predictions semi-seriously.  That way, I don't have a 98% failure rate. I have a 98% sarcasm rate.

Ulfarr

  • Bay Watcher
  • Going on a pilgrimage to Mars
    • View Profile
Re: Mathematics Help Thread
« Reply #2582 on: April 05, 2024, 04:03:45 am »

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.
Logged
Bring Kobold Kamp to LNP! graphics compatibility fix.

So the conclusion I'm getting here is that we use QSPs because dwarves can't pilot submarines.

JoshuaFH

  • Bay Watcher
    • View Profile
Re: Mathematics Help Thread
« Reply #2583 on: April 16, 2024, 03:37:37 pm »

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?
Logged

da_nang

  • Bay Watcher
  • Argonian Overlord
    • View Profile
Re: Mathematics Help Thread
« Reply #2584 on: May 18, 2024, 03:46:17 am »

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 a3 - b2 = b+1 and (b+1)2 - a3 = b, or alternatively, a3 - (b+1)2 = b and b2 - a3 = (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 4a3-3 must be a square number, and G is impossible since it implies b = (√(4a3+5)+1)/2 and b = (√(4a3+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 (73 - 182 = 19 and 192-73 = 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?
Logged
"Deliver yesterday, code today, think tomorrow."
Ceterum censeo Unionem Europaeam esse delendam.
Future supplanter of humanity.

Magmacube_tr

  • Bay Watcher
  • Praise KeK! For He is The Key and The Gate!
    • View Profile
Re: Mathematics Help Thread
« Reply #2585 on: May 18, 2024, 06:14:17 am »

What is 6 x 3?
Logged
I must submerge myself in MAGMAAAAAAAAA! daily for 17 cents, which I detest. With a new profile picture!

My gaem. JOIN NAOW!!!

My sigtext. Read if you dare!

zhijinghaofromchina

  • Bay Watcher
  • I am a fan of 矮人要塞
    • View Profile
Re: Mathematics Help Thread
« Reply #2586 on: May 18, 2024, 10:43:41 am »

根据乘法表口诀,三六一十八, so, I guess 3*6=18
Logged
人生在世不称意 明朝散发弄扁舟

NJW2000

  • Bay Watcher
  • You know me. What do I know?
    • View Profile
Re: Mathematics Help Thread
« Reply #2587 on: May 19, 2024, 01:02:12 pm »


By that I mean, is there a natural number b such that a3 - b2 = b+1 and (b+1)2 - a3 = b, or alternatively, a3 - (b+1)2 = b and b2 - a3 = (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:

Quote
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.
Logged
One wheel short of a wagon

da_nang

  • Bay Watcher
  • Argonian Overlord
    • View Profile
Re: Mathematics Help Thread
« Reply #2588 on: May 20, 2024, 01:12:29 pm »

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 4a3-3 = k2 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/41/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 4a3-3 = 4v2 <=> a3-3/4 = v2, 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 4a3-3-k2 = 0 (for now, assume the variables are real numbers). It has the real number solutions k = +-sqrt(4a3-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) = 4x3-3-y2, and let the algebraic curve be f(x,y)=0. The partial derivatives are ∂f/∂x = 12x2, 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 xi in A such that every element x in A can be written as a weighted sum of xi, 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 4a3-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.
« Last Edit: May 20, 2024, 01:29:39 pm by da_nang »
Logged
"Deliver yesterday, code today, think tomorrow."
Ceterum censeo Unionem Europaeam esse delendam.
Future supplanter of humanity.

McTraveller

  • Bay Watcher
  • This text isn't very personal.
    • View Profile
Re: Mathematics Help Thread
« Reply #2589 on: May 20, 2024, 04:21:32 pm »

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

b2 < a3 < (b+1)2

But you're looking for

a3 - b2 = b+1
(b+1)2 - a3 = b

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

So you are looking for cubes a3 that are b+1 bigger than b2.

So you are looking for cubes of the form a3 = b2 + b+1

If you define c = a3 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 + √(a3 - 3/4).

Maybe that helps...?

EDIT: fixed typo
« Last Edit: May 20, 2024, 04:29:02 pm by McTraveller »
Logged

hops

  • Bay Watcher
  • Secretary of Antifa
    • View Profile
Re: Mathematics Help Thread
« Reply #2590 on: May 20, 2024, 10:05:15 pm »

can someone ELI5 how/why the taylor series works?
Logged
she/her. (Pronouns vary over time.) The artist formerly known as Objective/Cinder.

One True Polycule with flame99 <3

Avatar by makowka

Maximum Spin

  • Bay Watcher
  • [OPPOSED_TO_LIFE] [GOES_TO_ELEVEN]
    • View Profile
Re: Mathematics Help Thread
« Reply #2591 on: May 20, 2024, 10:40:31 pm »

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 a3 - b2 = b+1 and (b+1)2 - a3 = b, or alternatively, a3 - (b+1)2 = b and b2 - a3 = (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 4a3-3 must be a square number, and G is impossible since it implies b = (√(4a3+5)+1)/2 and b = (√(4a3+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 (73 - 182 = 19 and 192-73 = 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)2 = x2 + 2x + 1, and (x2 + 2x + 1) - x2 = 2x + 1, which is the sum of x and x + 1. Therefore, it is sufficient that a3 = b2 + 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)2 is equal to b2 - 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 4a3-3 thing, that obviously makes (b + b + 1)2, 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 4a3-3 = k2 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/41/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 4a3-3 = 4v2 <=> a3-3/4 = v2, 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.
Quote
In summary then, per Siegel's theorem (if my math checks out), and assuming 4a3-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 (3n2 + 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.
Logged
Pages: 1 ... 171 172 [173]