Problem 425

[apscst]

Hi,

I get the good results for F(10**3) and F(10**4), but for F(10**7) I get a wrong result.

Can you confirm me that F(10**6) is *****9144 ?

Is there any special trick that doesn't reveal itself for 10**3 and 10**4? Do I have to look for something special? (Note: that is a Yes or No question )

Thanks

[sivakd]

I would think of it as a bug than a trick. Usually in situations like this best option is to review code thoroughly and if you have a bruit-force version, compare the results till you get an incorrect result and then debug. Incidentally, I happened to get correct result for 10^3 and 4 but incorrect result for 10^7. Took me a while to figure out I was changing digits from 1 to 9 instead of 0 to 9.

[apscst]

Thanks siva,

I'll look for the _bug_. That's precious information

I can't imagine a brute-force solution for this problem so I have to rely on the code review. I still can't see where my error is, but I'll continue to look for.

Bonne chance

[thundre]

Can you confirm me that F(10**6) is *****9144 ?

It is not.

[apscst]

Thanks all, I've finally solved this problem.

Actually, for 10**7 (10**6 too) there is happening something that do not happens for 10**3 or 10**4.

Good luck!

[ukimiku]

Are the primes 6007 and 7 considered 2's relatives? If the leftmost digit of 6007 is dropped, 007 remains, the value of which is 7.
EDIT: Nevermind, I reread the problem description which implies that 6007 and 7 are not considered 2's relatives.

Regards,

[mdean]

Are the primes 6007 and 7 considered 2's relatives? If the leftmost digit of 6007 is dropped, 007 remains, the value of which is 7.
EDIT: Nevermind, I reread the problem description which implies that 6007 and 7 are not considered 2's relatives.

Regards,

Why would 7 not be a 2's relative? Take 2, change 1 digit and voila, 7! As for 6007, maybe it is and maybe it isn't, but going from 7 to 6007 would be adding more than 1 digit.

[rblackadar]

I seem to have a different problem -- correct result for 10**3, but incorrect for 10**4; I'm getting 61175 instead of 78728. Does anyone recognize this incorrect value, and can you give me a hint on what I might be getting wrong? The frustrating thing is, I have identified 1202 primes under 10000 that are 2's relative, and apparently that is a few too many -- yet, I've looked at the generated paths-to-2 for all 1202 and they all look good to me. (And no, I'm not allowing any leading zeroes.)

[thundre]

The frustrating thing is, I have identified 1202 primes under 10000 that are 2's relative, and apparently that is a few too many -- yet, I've looked at the generated paths-to-2 for all 1202 and they all look good to me. (And no, I'm not allowing any leading zeroes.)

Some of those chains must be wrong. There are 3 categories of mistakes:

1. Bad link (more than one digit changed, or use of leading 0).
2. Number greater than start of chain.
3. Number is not prime.

You're adding up 27 primes to get that total, correct? If you PM me a sorted list of 27 primes, I'll tell you the first one you missed. Then you can re-examine the path.

[rblackadar]

Correct, my list for N=10000 is only 27 and thus must be incomplete. I even re-coded my solution, using a different method, and it gives the same wrong result. Very strange. So thanks, thundre, I really could use your help. PM sent.

[rblackadar]

Problem solved, thank you very much for your help, thundre. If there were a red-faced smiley I would use it here! I must have read the problem statement 100 times but never appreciated exactly what the words "to the left" meant. I think what happened was that I made the too-hasty assumption that "to the left of A (or B)" was equivalent to "to the left or right of A". Trivial to see that it is not, but apparently not so easy (at least for me) once that mistaken notion got unconsciously into my brain. Anyhow, I hope anyone else reading this thread in the future, and getting my bizarre result, will now know how to fix it.

[laqq3]

For the case 10^3, I get a sum of 433 instead of 431. Can someone clarify whether 2 is relative to 2? Thanks!

[souravran]

Hi,
I have some doubts about this problem, I would appreciate if someone helps me. My questions are below....
if we take this example 2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 107 ↔ 127
1> 5,7,11 won't be 2's relative, is it because the chain would be incomplete ?
2> why 103 is not 2's relative ?
3> If we consider prime numbers like 5 , 7 , 11 and so on, we will end up in many small chains. Do we have to take into account the largest chain ?

Thank you so much !!

[jaap]

if we take this example 2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 107 ↔ 127

2> why 103 is not 2's relative ?

The problem says:

We call a prime P a 2's relative if there exists a chain of connected primes between 2 and P and no prime in the chain exceeds P.

That example chain links 2 and 103 by going through a number larger than 103, namely 113, so that example chain does not make 103 a 2's relative. In fact there does not exist any chain between 2 and 103 without larger numbers, so 103 is not a 2's relative.

[dombiedoodle]

Wow, I did exactly the same thing-- correct answer for 10^3,
incorrect answer 61175 for 10^4. I was hesitant to read this thread thinking it would be too much of a spoiler, but now that I read it I'm glad I did. I could have read the problem description a million times and still missed the "to the left". Thanks.

[ravoorheis]

I'm getting a perplexing result with my brute force code that is leading me to believe I might be missing something with the logic. My script returns the correct result for F(10³), but for F(10⁴) it returns 80809, which is 2081 more than the correct answer. 2081 is one of the primes that is being counted in the result, but I can't find a way for 2081 to be 2's neighbor. I've verified each of the possible paths for the 43 primes in my sum by inspection and can't find a valid connection for any of them. I'm 100% certain that I'm checking all 1229 primes less than 10⁴, and I'm pretty sure that I'm not making any of the categories of mistakes that thundre lists above.

Is the following understanding of the problem correct for 2081?

The path cannot 'go through' any number higher than 2081, so for the first step the only possible valid rearrangements are 2011, 2021, 2031, 2041, 2051, 2061, 2071, 2080, and 1081.

Of these, only 2011 is prime. So any path must start with 2081 -> 2011

From 2011, the possible rearrangements that are smaller than 2081 could be 1011, 2001, 2010, the numbers 2012 through 2019 (and numbers of the form 20x1, but those possibilities have already been checked above and are not prime). Of these, the only prime is 2017.

This limits the possible paths to 2081->2011->2017

Using the same logic, I find the only possible connection from 2017 is 2027, and then that the only possibly connection from 2027 is 2017, which exhausts all possible paths.

So either my understanding of the problem is incorrect and 2081 is actually a 2's neighbor, or I'm incorrectly counting some primes and failing to count others, of which the total difference is 2081.

[Georg]

The path cannot 'go through' any number higher than 2081, so for the first step the only possible valid rearrangements are 2011, 2021, 2031, 2041, 2051, 2061, 2071, 2080, and 1081.

Of these, only 2011 is prime.

What are the prime factors of 2071?

[ravoorheis]

The path cannot 'go through' any number higher than 2081, so for the first step the only possible valid rearrangements are 2011, 2021, 2031, 2041, 2051, 2061, 2071, 2080, and 1081.

Of these, only 2011 is prime.

What are the prime factors of 2071?

That is easily checked with Google, Wolfram Alpha, or a factorize function that I would assume is in any Project Euler solver's toolkit: 109*19 = 2071.

(Edited for grammar and to remove unnecessary snark)

[mpiotte]

... So either my understanding of the problem is incorrect and 2081 is actually a 2's neighbor, or I'm incorrectly counting some primes and failing to count others, of which the total difference is 2081.

EDIT: incorrect response removed

[ravoorheis]

You are correct for 2081, it is not a 2's neighbor. The error must be elsewhere.

Lovely. That's what I was afraid of. Thanks for the confirmation.