A Strange Sequence not in the OEoIS

[David Harden]

The nth term of this sequence is the largest k such that k+1 is square and the largest prime factor of k is <= the nth prime.

This sequence is computable (but probably not efficiently so), and I will give the first three terms with proof for the third (proofs for the first two are much easier to obtain but harder to generalize): 8, 288, 25920

Proof that 25920 is the third term:

Suppose x^2 - 1 is the product of 2's, 3's and 5's. Then x^2 - 1 = Dy^2 where D is a subset product of {2,3,5}: 1,2,3,5,6,10,15, or 30. D=1 is eliminated trivially.

Note: If a and b are integers, then (a + b*sqrt(D))^k = a' + b'sqrt(D), where b' is a multiple of b. This is because this power lives not just in Z[sqrt(D)] but in the subring Z[b*sqrt(D)].

D=2: We wish to compute the largest x such that x^2 - 1 = 2y^2 and y factors over {2,3,5}. Since that equation can be rewritten as x^2 - 2y^2 = 1, this reduces to looking at units with norm 1 in Z[sqrt(2)]. Since we may, without loss of generality, assume that x and y are positive, this further reduces to looking at positive integral powers of 3 + 2sqrt(2).

(3 + 2sqrt(2))^2 = 17 + 12sqrt(2), which is admissible (i.e., all prime factors of 12 are 2, 3 or 5).
(3 + 2sqrt(2))^3 = 99 + 70sqrt(2), which is inadmissible because of the prime 7.

To handle prime exponents p > 3, let q be a prime factor of the coefficient of sqrt(2) in (3 + 2sqrt(2))^p. Then q divides ( (3 + 2sqrt(2))^p - (3 - 2sqrt(2))^p )/(4sqrt(2)), so (3 + 2sqrt(2))^p == (3 - 2sqrt(2))^p (mod q) in Z[sqrt(2)]. Then dividing by the right (which is permitted because 3 - 2sqrt(2) is a unit in Z[sqrt(2)]) yields 
(17 + 12sqrt(2))^p == 1 (mod q).
If q is odd, then we either have (2/q) = 1 or (2/q) = -1.
If (2/q) = 1, then the multiplicative group of Z[sqrt(2)]/(q) is isomorphic to the product of 2 cyclic groups of order q-1. Then the existence of an element of order p in the group means q == 1 (mod p), so q >= 2p + 1 >= 11. Otherwise 17 + 12sqrt(2) has order 1 and q divides 16 + 12sqrt(2), which is impossible if q is odd.
If (2/q) = -1, then the multiplicative group of Z[sqrt(2)]/(q) is cyclic of order q^2 - 1. Then the existence of an element of order p in the group means that q^2 == 1 (mod p) so q == +/- 1 (mod p). Then q >= 2p - 1 >= 9.
Also, the highest power of 2 dividing the coefficient of       sqrt(2) cannot increase upon passage to (3 + 2sqrt(2))^p, since the order of the multiplicative group of Z[sqrt(2)]/(4) is
8 and therefore pth powering is invertible in it.
Then, trivial estimates show that such a q congruent to +/-1 mod p must arise as a prime factor of the coefficient of sqrt(2) in (3 + 2sqrt(2))^p so any such unit is inadmissible. Moreover, this applies also to (3 + 2sqrt(2))^k whenever k is a multiple of some p > 3, by the Note. Therefore we need only check (3 + 2sqrt(2))^k, where k is the product of a power of 2 and a power of 3. Since 3 likewise confers inadmissibility, we only need to look at powers of 2.

(3 + 2sqrt(2))^4 = 577 + 408sqrt(2), which is inadmissible because of the prime 17.

Any larger power of 2 is a multiple of 4, 6 or 9, so we are done by using the Note again. The largest x^2 - 1 completely factorable over {2,3,5} obtained here is 17^2 - 1 = 288 < 25920.

D=3: Here, the norm 1 units are all powers of 2+sqrt(3).
(2 + sqrt(3))^2 = 7 + 4sqrt(3), which is admissible.
(2 + sqrt(3))^3 = 26 + 15sqrt(3), which is admissible.

p > 3 is eliminated from consideration by the same kind of reasoning as that used in the D=2 case.

(2 + sqrt(3))^4 = 97 + 56sqrt(3), which is admissible.
(2 + sqrt(3))^6 = 1351 + 780sqrt(3), which is inadmissible because of the prime 13.
(2 + sqrt(3))^9 = 70226 + 28305sqrt(3), which is inadmissible because of the prime 37.

(2 + sqrt(3))^8 = 18817 + 10864sqrt(3), which is inadmissible because of the prime 97. No further searching is needed, and the largest x^2 - 1 contributed here is 97^2 - 1 = 9408 < 25920.

D=5: Here, the norm 1 units with integral (and not half-integral) coeffcients of 1 and sqrt(5) are all powers of 
((1 + sqrt(5))/2)^6 = 9 + 4sqrt(5).
(9 + 4sqrt(5))^2 = 161 + 72sqrt(5), which is admissible.
(9 + 4sqrt(5))^3 = 2889 + 1292sqrt(5), which is inadmissible because of the prime 19.
(9 + 4sqrt(5))^p, for prime p > 3, is inadmissible as before, using the same kind of reasoning.

(9 + 4sqrt(5))^4 = 51841 + 23184sqrt(5), which is inadmissible because of the prime 23. We are done searching, and the largest x^2 - 1 contributed here is 161^2 - 1 = 25920.

D=6: Here we look at powers of 5 + 2sqrt(6).
(5 + 2sqrt(6))^2 = 49 + 20sqrt(6), which is admissible.
(5 + 2sqrt(6))^3 = 485 + 198sqrt(6), which is inadmissible because of the prime 11.
(5 + 2sqrt(6))^p, for prime p > 3, is inadmissible as before, using the same kind of reasoning.

(5 + 2sqrt(6))^4 = 4801 + 1960sqrt(6), which is inadmissible, because of the prime 7. We are done searching, and the largest x^2 - 1 contributed in this case is 49^2 - 1 = 2400 < 25920.

D=10: Here we look at powers of 19 + 6sqrt(10).

(19 + 6sqrt(10))^2 = 721 + 228sqrt(10), which is inadmissible because of the prime 19.
(19 + 6sqrt(10))^3 = 27379 + 8658sqrt(10), which is inadmissible because of the prime 37.
(19 + 6sqrt(10))^p, for prime p > 3, is inadmissible as before, using the same kind of reasoning.

We are done searching, and the largest x^2 - 1 contributed in this case is 19^2 - 1 = 360 < 25920.

D=15: Here we look at powers of 4 + sqrt(15).

(4 + sqrt(15))^2 = 31 + 8sqrt(15), which is admissible.
(4 + sqrt(15))^3 = 244 + 63sqrt(15), which is inadmissible because of the prime 7.
(4 + sqrt(15))^p, for prime p > 3, is inadmissible as before, using the same kind of reasoning.

(4 + sqrt(15))^4 = 1921 + 496sqrt(15), which is inadmissible because of the prime 31. We are done searching, and the largest x^2 - 1 contributed in this case is 31^2 - 1 = 960 < 25920.

D=30: Here we look at powers of 11 + 2sqrt(30).

(11 + 2sqrt(30))^2 = 241 + 44sqrt(30), which is inadmissible because of the prime 11.
(11 + 2sqrt(30))^3 = 5291 + 966sqrt(30), which is inadmissible because of the prime 7.
(4 + sqrt(15))^p, for prime p > 3, is inadmissible as before, using the same kind of reasoning.

We are done searching, and the largest x^2 - 1 contributed in this case is 11^2 - 1 = 120 < 25920.
The proof that 25920 is the third term of the sequence is complete.

I think, though I haven't checked, that the fourth and fifth terms are, respectively, 4801^2 - 1 = 23049600 and 19601^2 - 1 = 384199200.
An unusual aspect of computing multiple terms of the sequence is the reusability of computations of powers of the relevant units. For example, (5 + 2sqrt(6))^4 = 4801 + 1960sqrt(6) is inadmissible for the purpose of computing the third term of the sequence but admissible for the purpose of computing the fourth term of the sequence.

Another question: is this sequence strictly increasing?

---- David