PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 785,295,134
RAC: 433,522
Discovered 2 mega primesFound 1 prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,477,467)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,093,491)PPS LLR Sapphire: Earned 20,000,000 credits (27,357,246)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (34,191,283)SR5 LLR Turquoise: Earned 5,000,000 credits (6,110,877)SGS LLR Ruby: Earned 2,000,000 credits (3,486,285)TRP LLR Turquoise: Earned 5,000,000 credits (7,070,795)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (386,859,952)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Turquoise: Earned 5,000,000 credits (6,616,128)GFN Emerald: Earned 50,000,000 credits (53,771,465)WW Gold: Earned 500,000 credits (932,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1534
ID: 306875
Credit: 35,660,505
RAC: 9,493
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (13,193,892)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 785,295,134
RAC: 433,522
Discovered 2 mega primesFound 1 prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,477,467)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,093,491)PPS LLR Sapphire: Earned 20,000,000 credits (27,357,246)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (34,191,283)SR5 LLR Turquoise: Earned 5,000,000 credits (6,110,877)SGS LLR Ruby: Earned 2,000,000 credits (3,486,285)TRP LLR Turquoise: Earned 5,000,000 credits (7,070,795)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (386,859,952)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Turquoise: Earned 5,000,000 credits (6,616,128)GFN Emerald: Earned 50,000,000 credits (53,771,465)WW Gold: Earned 500,000 credits (932,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 4.60, 3.06, 2.76
Generated 24 Sep 2021 | 15:13:26 UTC