A Number Theory Problem

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
A Number Theory Problem
Define an algorithm to generate n sequential composite numbers.
A composite number is an integer greater than 1 that is not prime.
n may be arbitrarily large.
It is sufficient to define the first composite number of the sequence.
It is necessary to prove each number of the sequence is composite.
It is not necessary to find the first (i.e. the sequence with the least possible starting
composite) such sequence.
For example, for the case n=5 the sequence 24, 25, 26, 27, 28 is a solution.
A composite number is an integer greater than 1 that is not prime.
n may be arbitrarily large.
It is sufficient to define the first composite number of the sequence.
It is necessary to prove each number of the sequence is composite.
It is not necessary to find the first (i.e. the sequence with the least possible starting
composite) such sequence.
For example, for the case n=5 the sequence 24, 25, 26, 27, 28 is a solution.

 New Member
 Posts: 7
 Joined: Wed May 01, 2013 4:35 am
Re: A Number Theory Problem
Are you posting this for our benefit or yours? If you need help with this problem it seems like pari/gp or SAGE would be well suited for your purposes. You can get fast prime testing that way. I wonder how well it would perform in practice for large n though. I suppose that since primes thin out rapidly past a certain point it might not be too bad.

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
Re: A Number Theory Problem
I know an answer to the problem. I only post this as a brain teaser for those interested in number theory, although answers different than the one I have in mind would be very interesting to me. My answer does not involve advanced mathematics in any way.
It is not clear to me that this problem necessarily relates to prime testing, fast or otherwise.
It is not clear to me that this problem necessarily relates to prime testing, fast or otherwise.

 New Member
 Posts: 7
 Joined: Wed May 01, 2013 4:35 am
Re: A Number Theory Problem
IBelieve wrote:It is not clear to me that this problem necessarily relates to prime testing, fast or otherwise.
I thought you wanted a practical algorithm. The most practical way to do this sort of thing would be with fast prime tests. If a number that is greater than one fails the prime test, it can be potentially included in the sequence.
But maybe that's not what you were looking for...
Anyway, I'm just gonna throw this out here since I have a nice segue: http://projecteuler.net/

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
Re: A Number Theory Problem
What you are suggesting is one solution to the problem:
x=0;
i=4; # smallest composite
do until x=n
x++;
if (i is prime) # by whatever means
x = 0;
i++;
enddo;
upon exiting do loop, last composite in sequence is i1.
I am looking for more elegant solutions, perhaps involving a first composite given in a closed form, i.e. an expression that can be directly computed for a given n (at least conceptually, since n can be arbitrarily large).
Note also that the original problem statement makes no claims and places no qualifications on numbers outside of the sequence of n composites. So, for example, the sequence need not be tightly packed between prime numbers.
x=0;
i=4; # smallest composite
do until x=n
x++;
if (i is prime) # by whatever means
x = 0;
i++;
enddo;
upon exiting do loop, last composite in sequence is i1.
I am looking for more elegant solutions, perhaps involving a first composite given in a closed form, i.e. an expression that can be directly computed for a given n (at least conceptually, since n can be arbitrarily large).
Note also that the original problem statement makes no claims and places no qualifications on numbers outside of the sequence of n composites. So, for example, the sequence need not be tightly packed between prime numbers.
 Gord
 Real Skeptic
 Posts: 29090
 Joined: Wed Apr 29, 2009 2:44 am
 Custom Title: Silent Ork
 Location: Transcona
Re: A Number Theory Problem
I love brainteasers but I have little in the way of university level math. Alas! I coulda been a contendah! But I went into astronomy instead of math or honours physics.
We had a poster named Xouper who I think was good at this stuff, but he no longer posts here.
Not sure about any other highpost members.
We had a poster named Xouper who I think was good at this stuff, but he no longer posts here.
Not sure about any other highpost members.
"Knowledge grows through infinite timelessness"  the random fictional Deepak Chopra quote site
"You are also taking my words out of context."  Justin
"Nullius in verba"  The Royal Society ["take nobody's word for it"]
#ANDAMOVIE
"You are also taking my words out of context."  Justin
"Nullius in verba"  The Royal Society ["take nobody's word for it"]
#ANDAMOVIE

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
Re: A Number Theory Problem
The solution requires only multiplication and division.
To show that a number is composite requires only finding a divisor (other than 1 or the number itself) of the number.
Hint:
Suppose that the first number in the sequence is some function of n, say f(n). Then the second number of the sequence is f(n)+1, etc. Then consider some member of the sequence, say f(n) + k. How can we choose f(n) such that f(n) + k can be shown to be composite?
To show that a number is composite requires only finding a divisor (other than 1 or the number itself) of the number.
Hint:
Suppose that the first number in the sequence is some function of n, say f(n). Then the second number of the sequence is f(n)+1, etc. Then consider some member of the sequence, say f(n) + k. How can we choose f(n) such that f(n) + k can be shown to be composite?
 Hex
 Frequent Poster
 Posts: 1082
 Joined: Tue Mar 29, 2005 11:26 pm
 Custom Title: mi malam ciuj el vi
 Location: Ontario, Canada
Re: A Number Theory Problem
Gord wrote:Not sure about any other highpost members.
Are you suggesting that high posters on this forum are the only ones that are smart?
Spoiler:
 fromthehills
 Has More Than 9K Posts
 Posts: 9890
 Joined: Wed Aug 19, 2009 2:01 am
 Location: Woostone
Re: A Number Theory Problem
I saw the title and had a bit of a fright. I thought the problem was going to be in ESL about Jesus healing someone.
 fromthehills
 Has More Than 9K Posts
 Posts: 9890
 Joined: Wed Aug 19, 2009 2:01 am
 Location: Woostone
Re: A Number Theory Problem
Hex wrote:Gord wrote:Not sure about any other highpost members.
Are you suggesting that high posters on this forum are the only ones that are smart?
High thread count doesn't seem to correlate, either.
 Gord
 Real Skeptic
 Posts: 29090
 Joined: Wed Apr 29, 2009 2:44 am
 Custom Title: Silent Ork
 Location: Transcona
Re: A Number Theory Problem
Hex wrote:Gord wrote:Not sure about any other highpost members.
Are you suggesting that high posters on this forum are the only ones that are smart?
No, the opposite. I'm only sure about the lowpost members!
"Knowledge grows through infinite timelessness"  the random fictional Deepak Chopra quote site
"You are also taking my words out of context."  Justin
"Nullius in verba"  The Royal Society ["take nobody's word for it"]
#ANDAMOVIE
"You are also taking my words out of context."  Justin
"Nullius in verba"  The Royal Society ["take nobody's word for it"]
#ANDAMOVIE

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
Re: A Number Theory Problem
Suppose that the first number in the sequence is some function of n, say f(n). Then the second number of the sequence is f(n)+1, etc. The n term sequence is:
f(n), f(n)+1, f(n)+2, f(n)+3, ..., f(n)+n2, f(n)+n1.
Then consider some member of the sequence, say f(n) + k, k<n. How can we choose f(n) such that f(n) + k can be shown to be composite?
Try f(n) = k x n. Then f(n) + k = kn + k = k(n+1), which is clearly a composite number since it is written as the product of two integers, neither of which is 1. Now consider the kth term, f(n)+k+1. By extension try f(n) = k(k+1)n. Now the kth term can be written as (k+1)[(n)(k)+1] and previous term as (k)[(n)(k+1)+1]. By considering each value of k >=2 and k<n, we see that f(n)= (2)(3)(4)...(n2)(n1). The right hand side of this equation is known as the factorial of (n1), written (n1)!. So the first term of our sequence can be written as (n1)!. This is close to the final answer but the first two members  f(n) and f(n)+1  require special attention. [This is origin of the number 2 in the k>=2 relation above.] if we try to factor the term (n1)! + 1 using the approach used earlier, we arrive at 1 x [(n1)! + 1], which has not been shown to be composite since one of the factors is 1. To avoid this problem the sequence is simply started at f(n)+2 instead of f(n). Then the final term of the sequence becomes (n1)! + n + 1. However, (n1)! is not necessarily divisible by (n+1), so the factorial argument is increased by two as well.
The final answer 
The first term of the n term sequential series of composites is (n+1)! + 2. The last term is (n+1)! + n + 1.
f(n), f(n)+1, f(n)+2, f(n)+3, ..., f(n)+n2, f(n)+n1.
Then consider some member of the sequence, say f(n) + k, k<n. How can we choose f(n) such that f(n) + k can be shown to be composite?
Try f(n) = k x n. Then f(n) + k = kn + k = k(n+1), which is clearly a composite number since it is written as the product of two integers, neither of which is 1. Now consider the kth term, f(n)+k+1. By extension try f(n) = k(k+1)n. Now the kth term can be written as (k+1)[(n)(k)+1] and previous term as (k)[(n)(k+1)+1]. By considering each value of k >=2 and k<n, we see that f(n)= (2)(3)(4)...(n2)(n1). The right hand side of this equation is known as the factorial of (n1), written (n1)!. So the first term of our sequence can be written as (n1)!. This is close to the final answer but the first two members  f(n) and f(n)+1  require special attention. [This is origin of the number 2 in the k>=2 relation above.] if we try to factor the term (n1)! + 1 using the approach used earlier, we arrive at 1 x [(n1)! + 1], which has not been shown to be composite since one of the factors is 1. To avoid this problem the sequence is simply started at f(n)+2 instead of f(n). Then the final term of the sequence becomes (n1)! + n + 1. However, (n1)! is not necessarily divisible by (n+1), so the factorial argument is increased by two as well.
The final answer 
The first term of the n term sequential series of composites is (n+1)! + 2. The last term is (n+1)! + n + 1.
Who is online
Users browsing this forum: No registered users and 2 guests