Project Euler Forum

I guess I don't understand this problem as well as I thought I did.

In the example E(10), since it's uniformly chosen, there are 4 primes with a combined score of 8, so 8/4 = 2, which matches the result. However, when I do E(30), I get 2.7, and not 2.9 as suggested.

What am I missing/misunderstanding?

Thanks.

I'm not sure what "combined score" is, but if it's count of "1" in binary representation of primes, and you divide it to number of primes, then that's not it. The problem works in a different way.

If this is the first time you try solving problems involving "optimal play" "maximize score", i think you should try some older problems first.

"the player always guesses to maximize their score"

That means that the player will use the information gained from the right/wrong answers to determine whether it is best to guess 1 or 0 next.

phatmo wrote: Fri Jan 05, 2024 9:07 pm I'm not sure what "combined score" is, but if it's count of "1" in binary representation of primes, and you divide it to number of primes, then that's not it. The problem works in a different way.

If this is the first time you try solving problems involving "optimal play" "maximize score", i think you should try some older problems first.

Thanks. The way I understood "uniformly chosen" is basically, if that's the case with a die, and you roll it 6 times, it would give you all 6 values. Perhaps I misunderstood that, however, if that's the case, the expected value of rollling the die would be (1+2+3+4+5+6)/6, hence, I'm guessing "1" for optimal score which gives me those (wrong) results. But in any case, I probably do not understand math logic fully. Can you recommend an older problem with same kind of math solving?

jaap wrote: Fri Jan 05, 2024 9:14 pm "the player always guesses to maximize their score"

That means that the player will use the information gained from the right/wrong answers to determine whether it is best to guess 1 or 0 next.

Thanks.

The way I read the problem description, the player will always choose 1. I presume the reason for that is that all primes except for 2 has the LSB set to 1. Also, the MSB will always be 1 as the number of bits are determined by the value.

EDIT:

Even if I looked at the number of 0's and 1's in each prime, in the case of E(30), only 17 (10001) would have more 0's than 1's, so if I chose 0 as my guess on that number, it would bring my result to the E(30) to 2.8, which is still not 2.9.

KING-OLE wrote: Sat Jan 06, 2024 3:06 pm Can you recommend an older problem with same kind of math solving?

You may try Problem 232 (View Problem) and Problem 339 (View Problem).

KING-OLE wrote: Sat Jan 06, 2024 3:06 pm The way I read the problem description, the player will always choose 1

"uniformly chosen" means, if N=10 and there are 4 primes <= 10 (2,3,5,7), then probability of drawn prime = 2 (or 3 or 5 or 7) is 1/4.
For N=10, always choosing 1 is the best, but for other values of N like 30 or 10^8, that's not the best (At each guess, you can guess 0 or 1).
The way to understand the problem is, at the time you guess LSB is 0 or 1, you already have known what future would come to you (like, how many points you can get on avarege, until the game ends, if you guess 0, or 1 for LSB now). Hope this does not give away too much.

phatmo wrote: Sat Jan 06, 2024 4:34 pm

KING-OLE wrote: Sat Jan 06, 2024 3:06 pm Can you recommend an older problem with same kind of math solving?

You may try Problem 232 (View Problem) and Problem 339 (View Problem).

KING-OLE wrote: Sat Jan 06, 2024 3:06 pm The way I read the problem description, the player will always choose 1

"uniformly chosen" means, if N=10 and there are 4 primes <= 10 (2,3,5,7), then probability of drawn prime = 2 (or 3 or 5 or 7) is 1/4.
For N=10, always choosing 1 is the best, but for other values of N like 30 or 10^8, that's not the best (At each guess, you can guess 0 or 1).
The way to understand the problem is, at the time you guess LSB is 0 or 1, you already have known what future would come to you (like, how many points you can get on avarege, until the game ends, if you guess 0, or 1 for LSB now). Hope this does not give away too much.

Thanks for trying to help, but I'm still not quite getting this. If I "guess" 0 or 1 after looking at the number of 0's and 1's, I would only choose 0 on the prime 17. If I choose both 0 and 1 on those 10 primes, getting 20 scores, those would sum up to 38 but divided by 20 would be even further from the expected result. I'll try to look at p232 and p339. Thanks again.

EDIT:

I do understand "uniformly chosen" and this was confirmed by a chatbot. So again, if I use that logic and roll a 6-sided die 6 times, I should get each side-value once, getting a total score of 1+2+3+4+5+6 and the expected result would be 21/6 = 3.5.

The choices I have to choose 1 or 0 are:

- Always choose 1
- Always choose 0
- Choose 0 or 1 with equal random
- Choose 0 or 1 depending on the which occurs in the number most (kind a cheating)

EDIT 2:

Looked at the 2 suggested problems, and they would be harder for me than this I think. Probability math is one of the hardest areas for me, and it doesn't help that precise floating point calculations are slow and not really precise enough. I may just put this one on the shelf and pick a different one for now.

Thanks again for your help.

KING-OLE wrote: Sat Jan 06, 2024 5:00 pm Looked at the 2 suggested problems, and they would be harder for me than this I think. Probability math is one of the hardest areas for me, and it doesn't help that precise floating point calculations are slow and not really precise enough. I may just put this one on the shelf and pick a different one for now.

Sure. I just sent you an explanation about the problem. When you come back to this problem, you may take a look. Hope this help