My Math Forum Primes and Factoring

 Number Theory Number Theory Math Forum

 March 30th, 2018, 03:35 PM #1 Newbie   Joined: Mar 2018 From: United States Posts: 22 Thanks: 0 Primes and Factoring One way to create an infinite sequence of prime numbers: Start with an odd prime. Find the first number whose 2-cycle has a length equal to that prime. That will be your next prime. Repeat the above. Example: 11, 23, 47, . . . .
 March 30th, 2018, 04:35 PM #2 Senior Member   Joined: Sep 2016 From: USA Posts: 413 Thanks: 227 Math Focus: Dynamical systems, analytic function theory, numerics Another way to generate a list of infinite primes is to start with any prime and find the first number larger than it which is also prime. That will be your new prime. Repeat the above. Example: 7,11,13,... Also, what does the 2-cycle of an integer mean? Thanks from topsquark
March 30th, 2018, 05:38 PM   #3
Newbie

Joined: Mar 2018
From: United States

Posts: 22
Thanks: 0

Quote:
 Originally Posted by SDK Another way to generate a list of infinite primes is to start with any prime and find the first number larger than it which is also prime. That will be your new prime. Repeat the above. Example: 7,11,13,...
If you want to do that (find all of the primes larger than your starting prime) you might seek to confirm first that the sequence of primes is infinite - which is true. Then you will need to find the next prime.

In the method I presented there is no necessity to know at the start that there is an infinite number of primes. That will come out of the process. Nor will you have to verify that any given number is a prime. That also comes out of the process. What you do have to do is find the length of 2-cycles. Which brings me to:

Quote:
 Originally Posted by SDK Also, what does the 2-cycle of an integer mean?
The 2-cycle of an odd n is the multiplicative group generated by 2. That is, elements of the form 2^k mod n. The length is just the size of this group. Note that the length will be less than n.

For example, the 2-cycle for 7 is 2, 4, 1. Thus its length is 3.

Finally, I omitted details, so what I said was not intended to be a proof, just a statement.

 April 1st, 2018, 03:19 AM #4 Math Team   Joined: Jan 2015 From: Alabama Posts: 3,261 Thanks: 893 What you said originally was "Find the first number whose 2-cycle has a length equal to that prime. That will be your next prime.". The first number, after 3, that has 2-cycle equal to 3 is 7. But the next prime is 5, not 7.
April 1st, 2018, 05:23 AM   #5
Senior Member

Joined: May 2016
From: USA

Posts: 1,084
Thanks: 446

Quote:
 Originally Posted by Country Boy What you said originally was "Find the first number whose 2-cycle has a length equal to that prime. That will be your next prime.". The first number, after 3, that has 2-cycle equal to 3 is 7. But the next prime is 5, not 7.
Country Boy

I suspect that Penrose is not trying to construct a list of all primes. He is just trying to generate an infinite list of primes. Look at his first example.
11, 23, 47.

The list above ignores 13, 17, 19, 29, 31, 37, 41, and 43.

Penrose does not bother to prove his assertion. Nor does he explain what the mathematical utility of his list is. Indeed, he does not even explain how to apply his method. How is 23 related to the 2-cycle of 11?

April 1st, 2018, 06:59 AM   #6
Newbie

Joined: Mar 2018
From: United States

Posts: 22
Thanks: 0

Quote:
 Originally Posted by JeffM1 Country Boy I suspect that Penrose is not trying to construct a list of all primes. He is just trying to generate an infinite list of primes. Look at his first example. 11, 23, 47. The list above ignores 13, 17, 19, 29, 31, 37, 41, and 43.
This is true.

Quote:
 Originally Posted by JeffM1 Penrose does not bother to prove his assertion.
This also is true. But I don't want readers to lose interest because an initial post contains too much tedious detail. And a particularly energetic reader might even look for a counterexample. I will include a snippet of code below to help out.

Quote:
 Originally Posted by JeffM1 Nor does he explain what the mathematical utility of his list is.
But is it interesting? And is it true?

Quote:
 Originally Posted by JeffM1 Indeed, he does not even explain how to apply his method. How is 23 related to the 2-cycle of 11?
It's the cycle length of 23 that we want to look at here. That length is 11. There is a story behind that, but this post is already getting too long.

This code is VBA and runs on a spreadsheet, but anyone can easily translate to their favorite language.

Option Explicit
Dim i As Long
Dim j As Long
Dim k As Long
Dim n As Long
Dim CyclicValue As Long
Dim CyclicOrder As Long
Dim row As Long
Dim col As Long

Sub CycleOne()
row = 5
col = 1
n = 23
Cells(1, col) = n
CyclicValue = 2
Cells(4, col) = CyclicValue
CyclicOrder = 1
Do
CyclicValue = (2 * CyclicValue) Mod n
Cells(row, col) = CyclicValue
CyclicOrder = CyclicOrder + 1
If CyclicValue = 1 Then
Cells(2, col) = CyclicOrder
Exit Do
End If
row = row + 1
Loop
End Sub

Output:
23
11

2
4
8
16
9
18
13
3
6
12
1

April 1st, 2018, 02:05 PM   #7
Senior Member

Joined: Aug 2012

Posts: 1,971
Thanks: 550

Quote:
 Originally Posted by penrose One way to create an infinite sequence of prime numbers: Start with an odd prime. Find the first number whose 2-cycle has a length equal to that prime. That will be your next prime. Repeat the above. Example: 11, 23, 47, . . . .
Interesting idea. How do you know there even is such a next prime? That is, given prime $n$, how do we know that there is some subsequent odd number $m$ with $ord_2(m) = n$, let alone that $m$ is prime, where $ord_2(m)$ is the multiplicative order of $2$ mod $m$?

These numbers get big quickly. After 47 I found 2351 and then 4703, is that what you get? After that I could not find the next one in a search up to $100,000$. How far do I have to go, and how do I know I can find some $n$ such that $ord_2(n) = 4703$, let alone that it must be prime?

It would be interesting to have a proof or a counterexample about your conjecture. First, is it true that we can always find the next number in this sequence? And if so, must it be prime?

(Edit) My slow Python program is chugging along and hasn't found the next number after 4703 under 162,000. Now I have to either spend the rest of the day optimizing my program, which still won't help because I have no way of knowing if there even is a next number after 4703. Or perhaps someone has some clever theoretical ideas here ... or perhaps OP can say if he got to 4703 and what happened next.

Last edited by Maschke; April 1st, 2018 at 03:04 PM.

 April 1st, 2018, 03:23 PM #8 Banned Camp   Joined: Apr 2016 From: Australia Posts: 244 Thanks: 29 Math Focus: horses,cash me outside how bow dah, trash doves I too was once a huge fan of making quirky observations and limiting the detail of my explanation as a means of avoiding saying something silly which has a negative impact on the perception I want to give the reader, that I understand all details of my initial statement and the reader must bow to me in all my glory. But I changed my mind and decided I prefer explicit rigorous explanation and proof of every result I present, if I cannot do so or cannot be bothered in that instance, it becomes the question of a competition for which participants win nothing, but were originally promised a prize that only the lower class or homeless may appreciate. Anyway repost a rigorous explanation in 24 hours, or I am going to every park in my locality and throwing sand in children's eyes.
April 1st, 2018, 07:03 PM   #9
Senior Member

Joined: May 2016
From: USA

Posts: 1,084
Thanks: 446

Quote:
 Originally Posted by penrose Start with an odd prime. Find the first number whose 2-cycle has a length equal to that prime. That will be your next prime.
Only if it is indeed a prime, and even then it is misleading to say it is the next prime.

In any case, you need to prove that the indicated number is necessarily a prime. Please do so.

April 2nd, 2018, 02:37 AM   #10
Newbie

Joined: Mar 2018
From: United States

Posts: 22
Thanks: 0

Quote:
 Originally Posted by Maschke Interesting idea. How do you know there even is such a next prime? That is, given prime $n$, how do we know that there is some subsequent odd number $m$ with $ord_2(m) = n$, let alone that $m$ is prime, where $ord_2(m)$ is the multiplicative order of $2$ mod $m$?
That is important for sure, and I will have to do some background discussion to clarify that. I hesitate to do too much until I am off moderation and posting in real time.

Quote:
 Originally Posted by Maschke These numbers get big quickly. After 47 I found 2351 and then 4703, is that what you get? After that I could not find the next one in a search up to $100,000$. How far do I have to go, and how do I know I can find some $n$ such that $ord_2(n) = 4703$, let alone that it must be prime?
Yes, they can get very large quickly. 2351 and 4703 look good to me, and there are simplifications available, but we will be looking at more interesting problems in the future, so I would stop there.

Quote:
 Originally Posted by Maschke It would be interesting to have a proof or a counterexample about your conjecture. First, is it true that we can always find the next number in this sequence? And if so, must it be prime? (Edit) My slow Python program is chugging along and hasn't found the next number after 4703 under 162,000. Now I have to either spend the rest of the day optimizing my program, which still won't help because I have no way of knowing if there even is a next number after 4703. Or perhaps someone has some clever theoretical ideas here ... or perhaps OP can say if he got to 4703 and what happened next.
Stay tuned, we will get down to the nitty gritty.

 Tags factoring, primes

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mobel Number Theory 2 September 21st, 2015 01:44 PM matheist Number Theory 3 October 30th, 2014 05:52 PM caters Number Theory 67 March 19th, 2014 04:32 PM agustin975 Number Theory 11 March 10th, 2013 05:40 AM billymac00 Number Theory 4 November 22nd, 2009 04:05 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top