A134555 Values of n for which there is no optimal-length continued fraction expansion for sqrt(n) which is also symmetric (palindromic).

29, 53, 58, 85, 97, 125, 137, 173, 229, 241, 293, 298, 314, 338, 353, 365, 397, 425, 445, 457, 533, 538, 541, 554, 593, 629, 634, 641, 661, 733, 746, 769, 829, 845, 857, 877, 941, 965, 970, 977, 985, 997, 1010, 1042, 1061, 1082, 1093, 1114, 1130, 1138

Offset: 1

Author

Jim White (James.White(AT)maths.anu.edu.au), Nov 01 2007

Keywords

• nonn

Comments

These are the positive n for which there is no OCF (optimal-length continued fraction expansion of sqrt(n)) which remains purely symmetric.

All regular continued fraction (RCF) expansions for sqrt(n), n not a square, are half-period palindromes. For n = 29, for example: RCF(29) = [5, 2, 1, 1, 2, 10]

These are periodic CF's - the sequence of quotients, excepting the first, is repeated ad infinitum.

The repeated sequence, excepting the last, is always symmetric (palindromic).

The symmetry property is not guaranteed for all equivalent CF's, however.

OCF's are alternate (but still periodic) sequences representing the same value but in a sequence of minimum possible length. OCF's are found to have no quotients with the value 1 (all CF's containing 1's are contractable).

OCF's are not necessarily unique and in an ever-increasing majority of cases, there is an OCF for sqrt(n) which is itself symmetric in turn. Symmetry is of computational advantage, allowing final values to be predicted in half the number of steps, so the optimal-length CF might not necessarily be the most "efficient".

This sequence lists those values of n which do not permit a symmetric OCF. For example, with n = 29 as above, there are 4 OCF representations:

1: [5, 2, 2, -3, 10]

2: [5, 3, -2, -2, 10]

3: [5, 3, -3, 2, 10]

4: [6,-2, 3, -3, 12]

None of these have the symmetric property. They are, however, the result of a simple contraction of a symmetric CF just one element longer.

They arise for n where the RCF is of the form [a, ... b, 1, 1, b, ... 2a]

This can be contracted to a form like this: [a, ... c, -2, d, ... 2a] where c and d have opposite signs and have absolute values b and b+1, in either order.

This contraction is the only such case where symmetry is necessarily compromised.

A. A. Krishnaswami Ayyangar identified the "Nearest Square" CF, or NSCF, as being the CF implied by the "Indian cyclic method" for solving Pell's equation.

The NSCF algorithm will always identify an OCF - furthermore, it will always identify a symmetric one, unless that is not possible. This sequence identifies those exceptions.

The density of these "Krishnaswami numbers" is ever-decreasing. That is, the probability that n is a K-number tends to zero.

All (K-numbers) are of the form n = a, or n=2a, where a is composed only of prime divisors having form p=4k+1. This is not a sufficient condition, however, but it does mean that these numbers are a subset of the sums-of-squares.

Examples

			sqrt(29) has regular CF expansion [5, 2, 1, 1, 2, 10]. The sequence 2,1,1,2,10 is repeated ad infinitum. The central sequence "2, 1, 1, 2" is symmetric (a palindrome).
There are 4 shorter (and irregular) CF's for the same value:
[5, 2, 2, -3, 10]
[5, 3, -2, -2, 10]
[5, 3, -3, 2, 10]
[6,-2, 3, -3, 12]
The central sequence is asymmetric in all cases.
		

References

• A. A. Krishnaswami Ayyangar, New light on Bhaskara's chakravala or cyclic method of solving indeterminate equations of the second degree in two variables, Journal of the Indian Mathematical Society, 1929-30, Vol.18
• A. A. Krishnaswami Ayyangar, Theory of the Nearest-Square Continued Fraction, The Half-Yearly Journal of the Mysore University, Vol.1, No. 1 (1940) and Vol.1, No. 2 (1941)

Links

• Background and access to scanned versions of these papers is available at Historical work of A. A. K. Ayyangar.