## A Number Theory Problem

If the red house has blue shutters and the green house has red shutters, what's this section for?
IBelieve
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.

Naffat
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.

IBelieve
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.

Naffat
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/" onclick="window.open(this.href);return false;

IBelieve
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 i-1.

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
Obnoxious Weed
Posts: 35094
Joined: Wed Apr 29, 2009 2:44 am
Custom Title: prostrate spurge
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 high-post members.
"Knowledge grows through infinite timelessness" -- the random fictional Deepak Chopra quote site
"Imagine an ennobling of what could be" -- the New Age BS Generator site
"You are also taking my words out of context." -- Justin
"Nullius in verba" -- The Royal Society ["take nobody's word for it"]
#ANDAMOVIE
Is Trump in jail yet?

IBelieve
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?

Hex
Frequent Poster
Posts: 1136
Joined: Tue Mar 29, 2005 11:26 pm
Custom Title: mi malam ciuj el vi

### Re: A Number Theory Problem

Gord wrote:Not sure about any other high-post members.
Are you suggesting that high posters on this forum are the only ones that are smart?
Spoiler:

fromthehills
True Skeptic
Posts: 10902
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
True Skeptic
Posts: 10902
Joined: Wed Aug 19, 2009 2:01 am
Location: Woostone

### Re: A Number Theory Problem

Hex wrote:
Gord wrote:Not sure about any other high-post 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
Obnoxious Weed
Posts: 35094
Joined: Wed Apr 29, 2009 2:44 am
Custom Title: prostrate spurge
Location: Transcona

### Re: A Number Theory Problem

Hex wrote:
Gord wrote:Not sure about any other high-post 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 low-post members!
"Knowledge grows through infinite timelessness" -- the random fictional Deepak Chopra quote site
"Imagine an ennobling of what could be" -- the New Age BS Generator site
"You are also taking my words out of context." -- Justin
"Nullius in verba" -- The Royal Society ["take nobody's word for it"]
#ANDAMOVIE
Is Trump in jail yet?

IBelieve
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)+n-2, f(n)+n-1.

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)...(n-2)(n-1). The right hand side of this equation is known as the factorial of (n-1), written (n-1)!. So the first term of our sequence can be written as (n-1)!. 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 (n-1)! + 1 using the approach used earlier, we arrive at 1 x [(n-1)! + 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 (n-1)! + n + 1. However, (n-1)! is not necessarily divisible by (n+1), so the factorial argument is increased by two as well.