## A Number Theory Problem

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

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

### 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/

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

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:**30885**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 high-post 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 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

"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

### 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:**1118**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 high-post 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 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:**30885**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 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

"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

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

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)+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.

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 4 guests