wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> STRING OF PRIMES
        
(Message started by: pcbouhid on Nov 24th, 2005, 10:19am)
Title: STRING OF PRIMES
Post by pcbouhid on Nov 24th, 2005, 10:19am
Starting from an arbitrary prime of 3 digits you choose, construct a sequence of distinct 3-digit primes such that every one is formed by the 2 rightmost digits of the previous one plus any digit juxtaposed to the right - e.g. 113, 137, 373,... What is the maximum number of distinct primes that YOU can achieve in the sequence?

We are not asking for the maximum number of primes that can be achieved, we are asking for YOUR maximum number.
Title: Re: STRING OF PRIMES
Post by towr on Nov 24th, 2005, 10:31am
With or without the computer? ;D
Failing that, is a list of primes allowed, or should I do that from memory also?
Title: Re: STRING OF PRIMES
Post by pcbouhid on Nov 24th, 2005, 10:44am
towr, you can have at hand a list of primes, but the intention is to see who can achieve more primes without using a computer.
Title: Re: STRING OF PRIMES
Post by JocK on Nov 24th, 2005, 10:56am

on 11/24/05 at 10:44:43, pcbouhid wrote:
towr, you can have at hand a list of primes, but the intention is to see who can achieve more primes without using a computer.


Ok, let's make sure everyone starts from the same 'pole' position then.. ;)   (see attached list of 3-digit primes)
Title: Re: STRING OF PRIMES
Post by JocK on Nov 24th, 2005, 11:06am
It is not so difficult actually to get lengthy sequences. My first two trials (by hand) yielded:

113, 131, 311, (113 = repeat)

113, 131, 313, 137, 373, 733, 331, 317, 179, 797, 971, 719, 193, 937, 379, (797 =  repeat)

In most of the cases you have multiple choices for the next prime.
Title: Re: STRING OF PRIMES
Post by JohanC on Nov 24th, 2005, 11:14am
Following your wording, you would be allowed to use the same prime multiple times.
Although they don't count for calculating the maximum, they help to get a longer string.
Or did I read something wrong?
Title: Re: STRING OF PRIMES
Post by JocK on Nov 24th, 2005, 1:50pm

on 11/24/05 at 11:14:23, JohanC wrote:
Following your wording, you would be allowed to use the same prime multiple times.
Although they don't count for calculating the maximum, they help to get a longer string.
Or did I read something wrong?


If that is allowed, I am quite certain that one can get a sequence containing at least all 31 three digit primes that don't contain an even digit or the digit '5'...
Title: Re: STRING OF PRIMES
Post by towr on Nov 24th, 2005, 1:51pm
I don't feel like going further than
521 211 113 131 313 137 373 739 397 977 773 733 331 317 179 797 971 719 191 919 193 937 379
at the moment.
Title: Re: STRING OF PRIMES
Post by pcbouhid on Nov 25th, 2005, 6:11am
JohanC and jock, the problem states tacitly "construct a sequence of distinct 3-digit primes" .

And towr, thereīs at least one "longer" string than yours, with [hide]26[/hide] primes.
Title: Re: STRING OF PRIMES
Post by towr on Nov 26th, 2005, 1:38pm
Oh, I knew there were longer ones (well, strongly suspected as much at least). I just got tired of processing the list of primes by hand.
Title: Re: STRING OF PRIMES
Post by pcbouhid on Nov 27th, 2005, 4:28am
I understand. For this kind of puzzle, itīs better using a computer but, in a contest, to make it fair with the others, itīs not allowed. And this is not a contest.

A computer program found [hide]1820[/hide] sequences of [hide]26[/hide] primes, and 2 of them are:

[hide]241, 419, 191, 919, 193, 937, 373, 733, 331, 317, 179, 797, 977, 773, 739, 397, 971, 719, 199, 991, 911, 113, 131, 313, 137, 379.[/hide]

And:

[hide]941, 419, 199, 991, 919, 193, 937, 379, 797, 977, 773, 739, 397, 971, 719, 191, 911, 113, 131, 313, 137, 373, 733, 331, 317, 179.[/hide]
Title: Re: STRING OF PRIMES
Post by towr on Nov 27th, 2005, 7:30am
So is that the maximum then? Or wasn't it a complete search?

I had thought about drawing a graph of all candidate numbers and trying to find the longest path to visit each vertex at most once.
Which is also something a computerprogram might use.

Of course the first step is to seperate the primes of which the first two digits form an even number from those where it's odd. You can't use the first group anywhere except at the start. And you can throw out the few with a middle 0 completely.
Title: Re: STRING OF PRIMES
Post by pcbouhid on Nov 27th, 2005, 12:34pm
The computer program is not mine, but its result match the result found in another source ([hide]26 [/hide]primes).
Title: Re: STRING OF PRIMES
Post by herbs on Nov 28th, 2005, 7:38pm
None exist. The primes of Hebrew function H(x,Y,z)**2 over (a->x) make ( 137 373 739 397 977 773 733 331 317 179 797 971 719 191 919 193 937 379) invalid.
Title: Re: STRING OF PRIMES
Post by towr on Nov 29th, 2005, 1:12am

on 11/28/05 at 19:38:43, herbs wrote:
None exist. The primes of Hebrew function H(x,Y,z)**2 over (a->x) make ( 137 373 739 397 977 773 733 331 317 179 797 971 719 191 919 193 937 379) invalid.
Ah, now things are making sense.
You're just making things up and posting it under different names..  Naughty little troll ::)
Title: Re: STRING OF PRIMES
Post by Barukh on Nov 29th, 2005, 2:28am
towr, could you please explain herb's cryptic message, so that it will make sense for other members as well?

::)
Title: Re: STRING OF PRIMES
Post by towr on Nov 29th, 2005, 2:55am

on 11/29/05 at 02:28:36, Barukh wrote:
towr, could you please explain herb's cryptic message, so that it will make sense for other members as well?
It's sort of like technobabble; at first glance it sounds good but in actuallity it means nothing.
I think he's the same person that posted in (at least) two other threads.
Title: Re: STRING OF PRIMES
Post by pcbouhid on Nov 29th, 2005, 6:26am
See his comment in  "A SYSTEM OF MODULAR EQUATIONS".


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright Đ 2000-2004 Yet another Bulletin Board