[bonanova]

Can you construct an algorithm to produce a specified-length string of consecutive integers that are not prime?

For example, construct a string of 12 consecutive integers that are not prime.

Then construct the longest possible string of consecutive integers that are prime!

[Guest]

Can you construct an algorithm to produce a specified-length string of consecutive integers that are not prime?

For example, construct a string of 12 consecutive integers that are not prime.

Then construct the longest possible string of consecutive integers that are prime!

I can't quite do the first part right now, but for the second part...

1, 2, 3.

0,1,2,3 if you want to count 0.

Or 2,3 if you don't want to count 1.

Any other string will contain an even number which would be divisible by 2.

[Guest]

How are we gonna do this? Like a program algorithm?

[bonanova]

How are we gonna do this? Like a program algorithm?

A series of mathematical steps.

Whether you program it, actually, or do it by hand.

This problem you can do by hand - doesn't require the power of a computer.

[Guest]

y=2|i|+4

y will always be a positive even integer greater than 4 (all of which are not prime) for any integer value used for i.

[Guest]

I came up with 6, with i being the values 1-6

7,11,13,17,19,23

y= 3 + [ ( [ (i+1)%2 ] + 1) *2]

[unreality]

Is there a specification where we are unsure of the input. Can we specify a domain?

For example, for input (x) larger than 1, f(x) = 2x will work. But if we can't specify input, then it might not work (if x happened to be 1), and thus isn't "secure"

Likewise, do the numbers have to be integers? ie

f(x) x + .01 will make a non-integer which by default cannot be a prime. But if x happened to be 4.99, then it would fail.

So I'm saying, are we completely unsure of the input? In that case, I think this one works:

f(x) = -1 * |x|

where |x| is the absolute value of x. Unless you count -1 as a prime (its sole factors are itself and 1), this is guaranteed to work for all input, even if you rethread the answer into the next x to get 12 in a row

[Guest]

The set of integers includes both negative whole numbers and (positive) natural numbers; e.g. ..., -2, -1, 0, 1, 2, ... and prime numbers are natural numbers (i.e. only positive), so all the algorithm needs to do is print the first n consecutive negative whole numbers?

Edited January 9, 2009 by logic_chopper

[Guest]

These algorithms are a mixed of pascal and java.

this algol solve the first problem.

algorithm non-prime_Generator {

int l,i=0;int n=3; int[] s; //vars used

void test(int i,n; int[] s) { //procedure that test if a given odd number is prime and if its not then store it into S

int j,k;

For j=2 to (n-1)/2 do {

k=2*j-1;

if n%k=0 then {i=i++;s[i-1]=n;exit;}

}

//algol procedure

p[0]=3;

read(l);

while i<l+1 do {

n=++n;

if n%2=0 then {i=i++;s[i-1]=n;} else test(i,n,s); }

system.out.println("The string of integers is:");

for i=0 to l-1 do system.out.println(s);

this algol solve the second.

int [] prime; int i,j,k,l;

read(l);

prime[0]=2;

prime[1]=3

i=3;

k=0;

while k<l-1 do {

j=2*i-1;

for k=1 to high(prime) do {if j%prime[k]=0 then exit else

if k=high(prime) then {k=k++; prime[k]=j;} }

i=++i; }

system.out.println("the string of primes are:");

for i=0 to l-1 do system.out.println(prime);

[EventHorizon]

Can you construct an algorithm to produce a specified-length string of consecutive integers that are not prime?

For example, construct a string of 12 consecutive integers that are not prime.

Then construct the longest possible string of consecutive integers that are prime! http://brainden.com/forum/uploads/emoticons/default_wink.png' alt=';)'>

oops....forgot part 2

2,3

Let x be the number of consecutive composite numbers you want.

Let y = (x+1)! = (x+1) * x * (x-1) * (x-2) * ... * 1

The consecutive composite numbers are then y+2, ..., y+(x+1).

Hand wavy proof: Notice that y+2 is 2 more than a multiple of 2 (and therefore a multiple of 2 itself), y+3 is 3 more than a multiple of 3, etc.

Edited January 9, 2009 by EventHorizon

[bonanova]

oops....forgot part 2

2,3

Let x be the number of consecutive composite numbers you want.

Let y = (x+1)! = (x+1) * x * (x-1) * (x-2) * ... * 1

The consecutive composite numbers are then y+2, ..., y+(x+1).

Hand wavy proof: Notice that y+2 is 2 more than a multiple of 2 (and therefore a multiple of 2 itself), y+3 is 3 more than a multiple of 3, etc.

Yeah, that's it....

Nice.

[unreality]

so are these (specifically the one in the spoiler) not correct somehow?

[Prime]

oops....forgot part 2

2,3

Let x be the number of consecutive composite numbers you want.

Let y = (x+1)! = (x+1) * x * (x-1) * (x-2) * ... * 1

The consecutive composite numbers are then y+2, ..., y+(x+1).

Hand wavy proof: Notice that y+2 is 2 more than a multiple of 2 (and therefore a multiple of 2 itself), y+3 is 3 more than a multiple of 3, etc.

That is a nice economical solution. It is a corollary to Euclid’s proof that prime numbers are infinite. But the numbers are large. For 5 consecutive non-primes (or a prime gap of size 6), using that algorithm we find: {722, 723, 724, 725, 726}. Whereas, we know there are 5 consecutive non-primes between 23 and 29.

The OP requests an algorithm for finding a prime gap of a given size. The algorithm could be a simple search:

Suppose we look for a gap of size X (or X - 1) consecutive non-primes, where X > 3.

Find the prime number P nearest to and smaller than X. Starting with P+2 test consecutive numbers with the increment of 2 for being prime. When a prime is encountered and the gap from P is still less than X, repeat the search starting from the newly found prime plus two. (The algorithm saves some steps by skipping even numbers.)

This algorithm guarantees to find the first such gap that meets the OP requirement.

However, I don’t think that Bonanova had such an exhaustive search in mind as an answer to his problem. He must have been looking for an economical algorithm like the one that EH has suggested.

Is it possible to have an elegant non-exhaustive algorithm, which would find the very first gap of a given size? I say, since all prime numbers are arranged in a nice simple pattern with a certain kind of symmetry, such non-exhaustive algorithm exists. Although, it is a bit more complex than the one shown by EH...

P.S. This subject is so close to my heart. Bonanova has found my soft spot.

Edited January 10, 2009 by Prime

[Guest]

Is it possible to have an elegant non-exhaustive algorithm, which would find the very first gap of a given size? I say, since all prime numbers are arranged in a nice simple pattern with a certain kind of symmetry, such non-exhaustive algorithm exists. Although, it is a bit more complex than the one shown by EH...

Well, you could start by estimating the n^th prime number to be of order nln(n). You might therefore expect to find the first x consecutive non-primes somewhere in the neighborhood of x=(n+1)ln(n+1)-nln(n). That neighborhood could be pretty big however...

[Prime]

...

For example, construct a string of 12 consecutive integers that are not prime.

...

Starting with 3 all gaps between prime numbers are even (2, 4, 6, ...). Thus the number of intervenning integers is odd. So wherever there is a string of 12 consecutive non-primes, there are at least 13 such numbers. The very first gap of the size 14 is found between 113 and 127. This is gap is special in a way it is the maximal possible in a certain interval.

I believe Victor has already shown the exhaustive search that I mentioned in my previous post. It has been a good deal more than 30 years since I've seen anything written in Algol.

[unreality]

ohhhhh *slaps forehead* They have to be consecutive!

lol... I have to rethink now

[Prime]

Well, you could start by estimating the n^th prime number to be of order nln(n). You might therefore expect to find the first x consecutive non-primes somewhere in the neighborhood of x=(n+1)ln(n+1)-nln(n). That neighborhood could be pretty big however...

Did you see my new motto: "Natural numbers only, please"? Natural logarithm base is not a natural number. And I can see where you can get into logarithmic integrals from there. I categorically refuse to go into that higher math forest!

[Guest]

Did you see my new motto: "Natural numbers only, please"? Natural logarithm base is not a natural number. And I can see where you can get into logarithmic integrals from there. I categorically refuse to go into that higher math forest!

LOL!

(Gasp!) I have a contraband "i" in my closet too! Help me quick before the ATF find out!!!

[Prime]

These algorithms are a mixed of pascal and java.

this algol solve the first problem.

algorithm non-prime_Generator {

int l,i=0;int n=3; int[] s; //vars used

void test(int i,n; int[] s) { //procedure that test if a given odd number is prime and if its not then store it into S

int j,k;

For j=2 to (n-1)/2 do {

k=2*j-1;

if n%k=0 then {i=i++;s[i-1]=n;exit;}

}

//algol procedure

p[0]=3;

read(l);

while i<l+1 do {

n=++n;

if n%2=0 then {i=i++;s[i-1]=n;} else test(i,n,s); }

system.out.println("The string of integers is:");

for i=0 to l-1 do system.out.println(s);

this algol solve the second.

int [] prime; int i,j,k,l;

read(l);

prime[0]=2;

prime[1]=3

i=3;

k=0;

while k<l-1 do {

j=2*i-1;

for k=1 to high(prime) do {if j%prime[k]=0 then exit else

if k=high(prime) then {k=k++; prime[k]=j;} }

i=++i; }

system.out.println("the string of primes are:");

for i=0 to l-1 do system.out.println(prime);

The word "Algol" threw me off. I thought it was that old programming language I came across in 1970s. But it is not.

Anyway, I don’t see how the program here counts consecutive non-primes. I did not find where it resets its non-prime counter when it encounters a prime.

[Prime]

LOL!

(Gasp!) I have a contraband "i" in my closet too! Help me quick before the ATF find out!!!

Don't worry. "i" does not exist -- it's an imaginary thing.

BTW, there is a recent topic discussing Reimann's conjecture.