# Omnimaga

## General Discussion => Other Discussions => Math and Science => Topic started by: Xeda112358 on September 17, 2011, 11:56:49 am

Title: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 11:56:49 am
I have a little math challenge for y'all… This one isn't difficult so long as you don't overthink it, but if you do (like me) you will probably laugh at the simple solution. My hope is that you are like me and this keeps you occupied for a little while :

Find 132 consecutive composite natural numbers.

• Natural numbers are {1,2,3,4,…}
• A composite number is a number that isn't prime like 15 (15=3*5)
• An example of 12 consecutive composites is: {114,115,116,117,…,125,126}

I have two solutions that I came up with (one of them required Latex)
Have fun!?
Title: Re: A Math... Question :)
Post by: sqrt(Time) on September 17, 2011, 01:20:21 pm
I got an answer almost instantly, but that's just because I've seen this exact kind of problem done before. ^_^ (I guess that's cheating)
It is indeed fun...
I'm wondering what your second solution is?
Title: Re: A Math... Question :)
Post by: boot2490 on September 17, 2011, 01:38:42 pm
Here:
-132 through 0
Its too easy

P.S. I did overthink it. I looked of a list with 50 million prime numbers and couldn't find such a gap.

EDIT: Oh wait... those aren't natural...
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 01:41:42 pm
Is that a negative 132?
• Natural numbers are {1,2,3,4,…}
Also, such a gap does indeed exist :) In fact, there exists much more massive gaps :)

EDIT: Also, sqrt(Time), if you want to pm me your solution, feel free or you can wait until others have found it :D
Title: Re: A Math... Question :)
Post by: Ashbad on September 17, 2011, 01:44:29 pm
Hmm, I'll be interested to see a solution.  I've never seen this problem before, so I don't know the solution or a way to obtain it; hence, I've been playing around with some ideas in GHCi, to no current avail.
Title: Re: A Math... Question :)
Post by: boot2490 on September 17, 2011, 01:49:45 pm
Yeah,
m39 through that plus 132.
Primes.zip has a text file in it with all of the digits. It is over 4 megabytes.
Whoa.
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 01:50:23 pm
is that a mersenne prime (out of curiosity)?
Title: Re: A Math... Question :)
Post by: boot2490 on September 17, 2011, 01:57:40 pm
Si senor.
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 01:59:54 pm
Okay, well I do not have the computational power to test those values, but if you can show me that the next prime is greater than 133 digits away, I will accept that :) Note that if you are comparing, say, m34 to m35, that does not say that the next prime after m34 is m35 :) It just says that is the next mersenne prime
Title: Re: A Math... Question :)
Post by: boot2490 on September 17, 2011, 07:51:03 pm
m39 is THE LARGEST prime number known to man. If the next one was less than 133 away, we would have found it by now.
Also, What is your answer?

P.S. How is my sig? suggestions?
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 07:55:34 pm
Actually, that is not true :) That might be the largest known prime (I think there are a few larger ones that have been found), but there is a special algorithm for testing mersenne primes. This method couldn't be applied to the 134 values after it :)

(this is why not all of the values between mersenne primes have been tested)
Title: Re: A Math... Question :)
Post by: boot2490 on September 17, 2011, 08:00:34 pm
I see. So there are likely those higher but not mersenne.
So what is your answer?
Title: Re: A Math... Question :)
Post by: sammyMaX on September 17, 2011, 08:00:45 pm
Pretty easy. I got it!
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 08:03:31 pm
Well, I present you two answers...
Actually, only 1 since it was posted in IRC :) I will tell the other to Qwerty.55 if he wants, but I leave it up to you guys to find the other method :)

Theorem: If n and k are natural numbers where n is less than or equal to k, n|(k!+n)
Proof:
Let k and n be natural numbers
Since n is less than or equal to k, n is a factor of k!, so n|k!
Therefore, n|(k!+n)

A corollary follows that {k!+2,k!+3,k!+4,...,k!+k} is a sequence of k-1 composite numbers

So, if k=133, we have a sequence of at least 132 composite numbers :)
Title: Re: A Math... Question :)
Post by: flyingfisch on September 17, 2011, 10:24:02 pm
my solution was 10^120000 to 10^120000+132. (I wrote a prog in python to test that, since I was pretty sure there weren't many primes up there)
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 17, 2011, 10:27:29 pm
Hmm, could I see the code used to test it and is there any loss of accuracy when Python works with those numbers?
Title: Re: A Math... Question :)
Post by: sqrt(Time) on September 18, 2011, 02:33:51 pm
Well, I got a slight improvement... don't know if it really counts as different from the factorial solution, though. It has 51 digits, and goes 525...[45 digits]...632. (just to not spoil it for everyone else, while letting others check if they got the same solution)

edit for typo in a digit
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 18, 2011, 02:39:07 pm
Could you explain how you came to the result? The smallest value where a 134 digit gap or more occurs that I found (without factoring the values) was 57 digits long :/

(it should actually be a gap of more than 240)
Title: Re: A Math... Question :)
Post by: sqrt(Time) on September 18, 2011, 02:56:48 pm
Sent it in a PM.
Title: Re: A Math... Question :)
Post by: AngelFish on September 18, 2011, 03:00:02 pm
Hmm, could I see the code used to test it and is there any loss of accuracy when Python works with those numbers?

Python has BigNum libraries, so if the program was written correctly, the answer should be correct.
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 18, 2011, 03:20:10 pm
Ah, okay... Still, it isn't a pretty proof :P Also, sqrt(Time) is correct! Thanks for the proof, because that helped me make sense of it :)
Title: Re: A Math... Question :)
Post by: boot2490 on September 18, 2011, 03:24:42 pm
You seem to be very math savvy xeda! I mean, even your username is a reference to the Fibonacci sequence.
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 18, 2011, 03:26:59 pm
And my picture is a reference to Pascal's Triangle :D
Title: Re: A Math... Question :)
Post by: boot2490 on September 18, 2011, 03:27:58 pm
I thought that pascal's triangle was more one dimensional? It just goes down and expands in the middle.
I suppose lots of patterns in math usually lead to curves in the end. Think of the sines and waves and all that.
Title: Re: A Math... Question :)
Post by: Xeda112358 on September 18, 2011, 03:37:05 pm
Oh, the little curves are my own implementations :) It is the actual pieces that the curves "connect" to that are the pascals triangle part :) I drew it in paint, so I went down to the pixel
Title: Re: A Math... Question :)
Post by: boot2490 on September 18, 2011, 05:25:46 pm
Oh, I see... yeah, i see the triangle now. Cool!
I'm gonna use my psychic skills now... You did that in windows vista!
Title: Re: A Math... Question :)
Post by: phenomist on September 21, 2011, 01:06:53 am
Wait, how would you quickly test primality for 120000-digit numbers? If we could reliably do that, then let's go get that Ti-Nspire key now.

Title: Re: A Math... Question :)
Post by: Xeda112358 on September 21, 2011, 04:22:41 pm
Hehe, actually it is Windows 7 :P

@phenomist: Actually, it is relatively "easy" to check primality, it is "difficult" to factor. It was once thought that solving one would solve the other, but it has been proven that factoring and deterministic primality testing are two separate problems.

I am not too knowledgeable on the subject of the AKS deterministic primality test, but it puts Pascal's triangle to clever use and it is in fact polynomial time! The idea stems from polynomial expansion. I am sure you know how to expand (p+q)n by using Pascal's triangle (or nCr), but here is a really cool fact: Excluding the first and last element of a row in pascals triangle (so excluding the 1), all elements in row p are divisible by p if and only if p is prime. There is a neat little proof for that, but I don't have the patience to type it out :D

If you think about that, then in the expansion of (x+1)p where p is prime, all of the terms between the first and last will be divisible by p. (Wow, I think I finally understand the AKS primality test!  :w00t:) So what this means, is that if you do (x+1)p mod p, the only remaining terms are xp+1. The AKS primality test makes clever use of this :) Isn't this just lovely! Talking through this, I now actually understand the concept ! I think I could totally implement this, now!

But yeah, this doesn't help us factor numbers... hehe, yet 3:-)
Title: Re: A Math... Question :)
Post by: boot2490 on September 21, 2011, 07:02:41 pm
I gusses vista because of the color scheme, and that 7 is harder to use so the general public can't do stuff like that.
I have been using paint since before I could read. If there is something about it, I know it.
Title: Re: A Math... Question :)
Post by: flyingfisch on September 21, 2011, 07:04:16 pm
I have too. Its so simple, yet you can get pretty good graphics out of it (pixel art)
Title: Re: A Math... Question :)
Post by: boot2490 on September 22, 2011, 07:38:16 pm
Paint is very underrated.