## Other

drummers-lowrise

Message boards : General discussion : non-divisors of composites in n^2 - n - 1

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
composite
Volunteer tester

Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 785,295,134
RAC: 433,522

Message 119968 - Posted: 14 Aug 2018 | 5:50:54 UTC

n^2 - n - 1 is not one of the cyclotomic polynomials (but it looks very similar to one of them).

For integers n >= 3, x = n^2 - n - 1 is a sequence of prime and composite numbers. The first 10 elements of this sequence are 5, 11, 19, 29, 41, 55, 71, 89, 109, 131. There is nothing unusual about 9 of the first 10 elements in this sequence being prime - in the long run the number of primes among elements of this sequence decays logarithmically, just like the primes do among the full set of positive integers.

However, the interesting thing I noticed by looking at only the composite values of x, ASYMPTOTICALLY JUST ONE HALF OF ALL PRIMES ARE FACTORS OF COMPOSITE ELEMENTS OF THIS SEQUENCE. Prime numbers that never divide any of the composite values of x include: 2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, ... and this list is infinite.

For the asymptotic behaviour I checked values of n up to 1'000'003 at intervals of powers of 10 (plus 3): so at 4, 13, 103, 1'003, 10'003, 100'003, and 1'000'003. I'm currently checking 10'000'003. That's a relatively small n to make an asymptotic generalization, but I conjecture that the ratio converges non-monotonically to 1/2 as n increases, with an accuracy of about 1 part in sqrt(n).

It would be interesting, and perhaps exploitable for improving the efficiency of sieves, if this kind of relationship is found in other polynomials.

For the curious..., except for the number 2, all of these non-divisors end with the digit 3 or 7, and this holds as far as I have seen.

JeppeSN

Joined: 5 Apr 14
Posts: 1534
ID: 306875
Credit: 35,660,505
RAC: 9,493

Message 119969 - Posted: 14 Aug 2018 | 7:35:45 UTC

Primes can be either ±1 modulo 5 (will end in 1 or 9), or ±2 modulo 5 (will end in 3 or 7). The latter class is OEIS A003631. That entry has a comment:

Primes p such that the polynomial x^2-x-1 mod p has no zeros; i.e., x^2-x-1 is irreducible over the integers mod p. - T. D. Noe, May 02 2005
You may want to try to prove that!

Each class modulo 5 occurs with the same frequency asymptotically, that is the Prime number theorem for arithmetic progressions. So your hypothesis is correct.

/JeppeSN

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 785,295,134
RAC: 433,522

Message 119976 - Posted: 14 Aug 2018 | 13:48:14 UTC

I decided in the first post to show the integers with quotes to separate groups of 3 digits, like this: 10'000'003, rather than with commas as is customary in English-speaking world, or with periods as in most of Europe, or with spaces as in accounting. I don't recall seeing numbers expressed with quotes as digit group separators, but it's clearer to me to use quotes in the context of a sentence or a comma-separated list where commas and periods and spaces are used as other separators.

I think this convention would work well in a formula too. Quotes (or slanted tick marks) denote a variable's derivative or another version of a variable, and quotes are just not used with numbers.

Despite thinking so at first, surely I didn't innovate here. A quick search shows it is a sensible convention in at least 2 countries (Switzerland and Italy, although the latter can't seem to make up their minds on what to use). link

I wonder if I should keep using this notation for numbers, or if it's frying eyeballs and overloading neural circuits. It may play havoc with parsers reading CSV files, but otherwise the lack of comment so far is enouraging.

Message boards : General discussion : non-divisors of composites in n^2 - n - 1