Problem 329

jaap · Post by **jaap** » Sun Mar 20, 2011 7:08 am

Problem 329 (View Problem)

Does the frog croak for its starting square, or is its first croak for the square it lands on after its first jump?
(On rereading the question I'm pretty sure it does croak for the starting square. Was the wording changed or did I just fail at reading the first time?)

Also, there is a spelling error in the question: "croacks".

harryh · Post by **harryh** » Sun Mar 20, 2011 7:53 am

Yes, there is a croak for the first square too (the wording has not been changed).
Thanks for pointing out the spelling error - now fixed.

shachark · Post by **shachark** » Sun Mar 20, 2011 9:56 am

My strategy is comparing the given pattern to the probable pattern (according to a small prime sieve), and yet, although my fraction addition and reduction works fine, there seems to be some kind of a problem, the idea is comparing the first square, and the following 14 moves, right?

elr · Post by **elr** » Sun Mar 20, 2011 6:17 pm

you should remember that there are many different ways to reach the "probable pattern" ...

shachark · Post by **shachark** » Sun Mar 20, 2011 6:41 pm

Well, My algorithm calculates all the possible "walks", (The first move is 0 since first spot counts, and then +/-1), then I apply them on all starting positions (dropping those who exceed limitations of course), meanwhile, I determine probabilities by comparing the right pattern, to the wanted pattern. Did I understand correctly?

elr · Post by **elr** » Sun Mar 20, 2011 11:28 pm

seems so

just make sure that you calculate the probability exactly as the question describe

browni3141 · Post by **browni3141** » Mon Mar 21, 2011 12:01 am

I think I'm close. My random generator is slightly off from my proper solution though. Are these correct:
Probability of "P" == 119/300
"PP" == 230/1497
"PNPN" == 21271/322704

elr · Post by **elr** » Mon Mar 21, 2011 1:39 am

P is correct PP is not.

shachark · Post by **shachark** » Mon Mar 21, 2011 2:50 am

Well, I think I've found what the problem was, as my function was not a probability function (by definition, the sum wasn't 1), the only problem now is that the result is huge (really huge).

is the answer for "PPPP": 169783/6804000?

LarryBlake · Post by **LarryBlake** » Sun Mar 27, 2011 10:16 pm

No, sorry.

GenePeer · Post by **GenePeer** » Mon Mar 28, 2011 3:50 am

How many characters-long is the answer for "PPPPNNPP", including the (/)?

sivakd · Post by **sivakd** » Mon Mar 28, 2011 6:19 am

GenePeer · Post by **GenePeer** » Mon Mar 28, 2011 1:31 pm

Thanks! Now back #152...

ukimiku · Post by **ukimiku** » Thu May 12, 2011 10:45 am

Could someone please confirm that the probability for "PP" is 173/1125? I got "P" right, but my resulting fraction, though reduced, is awfully long...

Thank you.

Regards,

elr · Post by **elr** » Thu May 12, 2011 7:21 pm

that's a correct value !

jochenkeutel · Post by **jochenkeutel** » Fri May 25, 2012 4:59 pm

Can someone confirm that PPPP is 5537/324000 ?

jochenkeutel · Post by **jochenkeutel** » Sat May 26, 2012 12:50 pm

Please forget my last post: The number mentioned there is wrong.
I've found the correct solution now, also for the full string.

m4rius · Post by **m4rius** » Fri May 08, 2020 10:22 pm

Hello,
is it right to assume that the events "nth croak equals Xn", where Xn in {P, N}, are stochastically independent?
Because that's what I did and my solution seems to be wrong.
My idea was to first calculate Pn = P("frogs sits on a prime after n jumps"), P0 = 19/100 = 95/500, P1 = 24/125, P2 = 571/3000, ...
And then for n = 0..14 calculate
Qn = Pn x P("sits on a prime and croaks Xn") + (1 - Pn) x P("does not sit on a prime and croaks Xn") where X = PPPPNNPPPNPPNPN.
That is Qn should exactly be P("nth croak equals Xn") and the product of the Qn should be the solution. But it's not, so where am I wrong?

Best

sjhillier · Post by **sjhillier** » Fri May 15, 2020 3:58 pm

m4rius wrote: Fri May 08, 2020 10:22 pm is it right to assume that the events "nth croak equals Xn", where Xn in {P, N}, are stochastically independent?

I'm not sure I entirely understand the question, but I think the answer is "No".

Let's put it this way. If the frog started near the small numbers (around 5 say), the density of primes there is quite large, and so the probability of any sequence is different to the probability if it had started near (say) 250, where there are few primes. Taking an average prime distribution over the whole range is not going to capture the slightly different probabilites which arise from the actual local distribution where the frog (randomly) started.

karabonev · Post by **karabonev** » Tue May 10, 2022 8:21 am

I've been struggling with this problem for a while.
My answer for P is right but PP is a bit off.

Let P(x) be the chance to croak P on jump x.
P(1) = 119/300
I assume that the chance to hear PP is P(1) * P(2).
Previous posts suggest that the probability for PP is 173/1125 so I expect P(2)=692/1785.
However, I get P(2)=149/375.

Can anyone confirm if my assumption is correct?

Project Euler Forum

Problem 329

Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329

Re: Problem 329