You don't really need modular arithmetic, do you? If an arithmetic sequence contains m^2 and has common difference d, then it contains (m + kd)^2 for every integer k.
You can also "derive" the (m+kd)^2 result by directly trying to solve for integer solutions.
For fixed a and b, we want to find k and c such that a^2 + kb = c^2, or kb=c^2-a^2=(c+a)(c-a). We can do that by picking any c such that c-a is a multiple of b. Writing (c-a)=rb, we get that k=(c+a)r.
Plugging that back into the original equation, we get a^2+kb = a^2 + [(c+a)r]b = a^2 + [((rb+a)+a)r]b = a^2 + (rb+2a)rb = a^2+(rb)^2+2arb = (a+rb)^2.
Nice. That looks sufficient for proving the statement.
Can you prove there exist sequences with no squares? Do such sequences exist for any value of k > 2? This is where modular arithmetic might come in particularly handy.
The sequence 3 + 4n contains no squares, but I don't know how to prove that without basically using modular arithmetic. An odd square n² is the square of an odd number n = 2k+1, but (2k+1)² = 4(k²+k) + 1 is 1 more than a multiple of 4, whereas 3 + 4n never is.
I didn't see a full solution for the making the rounds, so here is one possible solution:
Every AP has the general form a+nd for n in Z. It follows, then, that *every* AP is equivalent to a single residue class {a} (mod d), assuming a is the minimal positive element.
If (a|d)=1, then {a} contains at least one square. But since the squares are periodic in any modulus, we can be sure that every d'th square is in {a}. That further implies that at least one (and usually two) residue class {b} (mod d) exists such that the squares of all terms inthe AP b+nd are in the AP a+nd.
For a concrete example, 4 is a QR mod 7. One of the modular square roots is clearly 2. So the squares of the terms in 2+7n: 2, 9, 16, 23... *all* have squares that are == 4 (mod 7), which you can easily check.
Meanwhile, 3 is a NR mod 7. Hence 3+7n contains no squares.
Clearly, every residue is either quadratic or non-quadratic, so the two possibilities are the only possibilities.
Generally an AP is assumed to be infinite in both directions. 90+% of the time, an AP is in Z or Q. While the problem statement didn't state those assumption explicitly, they're reasonable assumptions to make.
Actually. If you look at similar questions regarding squares in arithmetic progression, you will see that a lot of discussion surrounds finite progressions, i.e. tuples with constant difference.
You don't really need modular arithmetic, do you? If an arithmetic sequence contains m^2 and has common difference d, then it contains (m + kd)^2 for every integer k.
You can also "derive" the (m+kd)^2 result by directly trying to solve for integer solutions.
For fixed a and b, we want to find k and c such that a^2 + kb = c^2, or kb=c^2-a^2=(c+a)(c-a). We can do that by picking any c such that c-a is a multiple of b. Writing (c-a)=rb, we get that k=(c+a)r.
Plugging that back into the original equation, we get a^2+kb = a^2 + [(c+a)r]b = a^2 + [((rb+a)+a)r]b = a^2 + (rb+2a)rb = a^2+(rb)^2+2arb = (a+rb)^2.
Nice. That looks sufficient for proving the statement.
Can you prove there exist sequences with no squares? Do such sequences exist for any value of k > 2? This is where modular arithmetic might come in particularly handy.
The sequence 3 + 4n contains no squares, but I don't know how to prove that without basically using modular arithmetic. An odd square n² is the square of an odd number n = 2k+1, but (2k+1)² = 4(k²+k) + 1 is 1 more than a multiple of 4, whereas 3 + 4n never is.
I didn't see a full solution for the making the rounds, so here is one possible solution:
Every AP has the general form a+nd for n in Z. It follows, then, that *every* AP is equivalent to a single residue class {a} (mod d), assuming a is the minimal positive element.
If (a|d)=1, then {a} contains at least one square. But since the squares are periodic in any modulus, we can be sure that every d'th square is in {a}. That further implies that at least one (and usually two) residue class {b} (mod d) exists such that the squares of all terms inthe AP b+nd are in the AP a+nd.
For a concrete example, 4 is a QR mod 7. One of the modular square roots is clearly 2. So the squares of the terms in 2+7n: 2, 9, 16, 23... *all* have squares that are == 4 (mod 7), which you can easily check.
Meanwhile, 3 is a NR mod 7. Hence 3+7n contains no squares.
Clearly, every residue is either quadratic or non-quadratic, so the two possibilities are the only possibilities.
Nice! This was the sort of solution I had imagined.
The max values for f(N) look to me like (n / log(n))^(1/3) times a constant (perhaps between 15 and 16).
The "Making the Rounds" statement is surely false if the common difference is allowed to be either negative or irrational. Examples:
(1, -1, -3, -5, -7, -9, ...)
(1, 1 + sqrt(2), 1 + 2*sqrt(2), 1 + 3*sqrt(2), ...)
For sure. To make the statement interesting and more plausible, restrict the common difference (and the first term) to positive integers.
Generally an AP is assumed to be infinite in both directions. 90+% of the time, an AP is in Z or Q. While the problem statement didn't state those assumption explicitly, they're reasonable assumptions to make.
Actually. If you look at similar questions regarding squares in arithmetic progression, you will see that a lot of discussion surrounds finite progressions, i.e. tuples with constant difference.
Sure, because you can't have more than 3 consecutive squares in an arithmetic progression.
For Digits, do you have to generate a whole number for the final answer or are fractional values allowed?
Uh oh, that's a bad sign for my solution....
Submit a second time. It's okay!
Good question -- fractional values allowed! I'll update the post to clarify.