My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
Reply
 
LinkBack Thread Tools Display Modes
March 30th, 2018, 03:35 PM   #1
Newbie
 
Joined: Mar 2018
From: United States

Posts: 11
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, . . . .
penrose is offline  
 
March 30th, 2018, 04:35 PM   #2
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 354
Thanks: 192

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
SDK is offline  
March 30th, 2018, 05:38 PM   #3
Newbie
 
Joined: Mar 2018
From: United States

Posts: 11
Thanks: 0

Quote:
Originally Posted by SDK View Post
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.
penrose is offline  
April 1st, 2018, 03:19 AM   #4
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 3,091
Thanks: 846

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 is offline  
April 1st, 2018, 05:23 AM   #5
Senior Member
 
Joined: May 2016
From: USA

Posts: 990
Thanks: 406

Quote:
Originally Posted by Country Boy View Post
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?
Thanks from topsquark and penrose
JeffM1 is online now  
April 1st, 2018, 06:59 AM   #6
Newbie
 
Joined: Mar 2018
From: United States

Posts: 11
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
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
penrose is offline  
April 1st, 2018, 02:05 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,847
Thanks: 507

Quote:
Originally Posted by penrose View Post
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.
Maschke is online now  
April 1st, 2018, 03:23 PM   #8
Senior Member
 
Joined: Apr 2016
From: Australia

Posts: 243
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.
Adam Ledger is offline  
April 1st, 2018, 07:03 PM   #9
Senior Member
 
Joined: May 2016
From: USA

Posts: 990
Thanks: 406

Quote:
Originally Posted by penrose View Post
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.
JeffM1 is online now  
April 2nd, 2018, 02:37 AM   #10
Newbie
 
Joined: Mar 2018
From: United States

Posts: 11
Thanks: 0

Quote:
Originally Posted by Maschke View Post
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.
penrose is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
factoring, primes



Thread Tools
Display Modes


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





Copyright © 2018 My Math Forum. All rights reserved.