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

Postby IBelieve » Thu May 02, 2013 6:24 am

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

Postby Naffat » Thu May 02, 2013 7:14 am

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

Postby IBelieve » Thu May 02, 2013 7:37 am

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

Postby Naffat » Thu May 02, 2013 7:42 am

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/

IBelieve
New Member
Posts: 8
Joined: Wed May 01, 2013 11:08 am

Re: A Number Theory Problem

Postby IBelieve » Thu May 02, 2013 8:43 am

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.

User avatar
Gord
Real Skeptic
Posts: 29108
Joined: Wed Apr 29, 2009 2:44 am
Custom Title: Silent Ork
Location: Transcona

Re: A Number Theory Problem

Postby Gord » Thu May 02, 2013 10:15 pm

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
"You are also taking my words out of context." -- Justin
"Nullius in verba" -- The Royal Society ["take nobody's word for it"]
#ANDAMOVIE

IBelieve
New Member
Posts: 8
Joined: Wed May 01, 2013 11:08 am

Re: A Number Theory Problem

Postby IBelieve » Fri May 03, 2013 2:51 am

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?

User avatar
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

Postby Hex » Fri May 03, 2013 4:29 am

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:
  TOYNBEE IDEA
IN KUBRICK'S 2001
RESURRECT DEAD
ON PLANET JUPITER  

http://www.youtube.com/watch?v=fwoaOJZ7Dfk

User avatar
fromthehills
Has More Than 9K Posts
Posts: 9890
Joined: Wed Aug 19, 2009 2:01 am
Location: Woostone

Re: A Number Theory Problem

Postby fromthehills » Fri May 03, 2013 5:25 am

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.

User avatar
fromthehills
Has More Than 9K Posts
Posts: 9890
Joined: Wed Aug 19, 2009 2:01 am
Location: Woostone

Re: A Number Theory Problem

Postby fromthehills » Fri May 03, 2013 5:27 am

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.

User avatar
Gord
Real Skeptic
Posts: 29108
Joined: Wed Apr 29, 2009 2:44 am
Custom Title: Silent Ork
Location: Transcona

Re: A Number Theory Problem

Postby Gord » Fri May 03, 2013 6:44 am

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! :P
"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

IBelieve
New Member
Posts: 8
Joined: Wed May 01, 2013 11:08 am

Re: A Number Theory Problem

Postby IBelieve » Mon May 06, 2013 7:28 am

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.


Return to “Brainteasers”

Who is online

Users browsing this forum: No registered users and 1 guest