A253472 Square Pairs: Numbers n such that 1, 2, ..., 2n can be partitioned into n pairs, where each pair adds up to a perfect square.

4, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80

Offset: 1

Author

Henri Picciotto, Jan 01 2015

Keywords

• nonn

Comments

Kiran Kedlaya proved that all numbers greater than 11 are included in the sequence. Outline of proof:

- Show by hand or by computer that it works up to n = 30.

- For n=31, pair 62+59=61+60=11^2 and then reduce to the case of n=29. For n=32, pair 64+57, ..., 61+60 and reduce to the case of 28. And so on. This works until n=48.

- For n=49, ..., 72 pairs adding up to 13^2 allow us to reduce to n=35.

- Repeat the process, always terminating at (2m+1)^2-25, aiming for sums of (2m+3)^2. The first such pair is (2m+1)^2-23, 8m+31.

- This always works, as long as (2m+1)^2 - 25 > 8m+31, and therefore we must have m > 4.

A similar sequence using odd numbers can be created, by making n pairs that sum to perfect squares, using numbers from 0 to 2n-1. All numbers greater than 6 are included.

Worthy of consideration for the elementary school classroom working on square numbers. - Gordon Hamilton, Mar 20 2015

Examples

			For n = 4: (8, 1), (7, 2), (6, 3), (5, 4).
For n = 7: (14, 2), (13, 3), (12, 4), (11, 5), (10, 6), (9, 7), (8, 1).
		

References

• Alfred S. Posamentier, Stephen Krulik, Problem-Solving Strategies for Efficient and Elegant Solutions, Grades 6-12, 2008, page 191.

Links

• Gordon Hamilton, Kiran S. Kedlaya, and Henri Picciotto, Square-Sum Pair Partitions, College Mathematics Journal 46.4 (2015): 264-269.
• Thomas Kilkelly, The ARML Power Contest, 2015, page 77.
• Henri Picciotto, Python program to generate sequence
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A252897.

Programs

Python

# See link.

Formula

From Chai Wah Wu, Aug 13 2020: (Start)

a(n) = 2*a(n-1) - a(n-2) for n > 6.

G.f.: x*(-2*x^5 + 2*x^4 - 2*x^2 - x + 4)/(x - 1)^2. (End)