Problem 425

[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?

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.

That's right. I checked this list with my program that returned 2071 to be prime.
Checking again my program sometimes returnes 2071 = 2071 and sometimes 2071 = 19 * 109. I'll fix this.

[ravoorheis]

I just painstakingly went through each of the primes less than 10⁴, and verified that my list cannot possibly be 2's relatives. But the sum of them is still adding up to 80809. Could anyone confirm that there are 43 primes less than 10⁴ that are not 2's relatives - or would someone be willing to tell me via pm which of my primes is a 2's relative? Totally understandable if that would be giving away too much - it's on me to debug my own code.

[mpiotte]

My apologies. I made a mistake above. I should have checked with my program before answering.
I think what you are looking for is the following sequence:
2, 3, 13, 113, 103, 109, 1109, 1009, 1039, 2039, 2029, 2027, 2017, 2011, 2081.

[ravoorheis]

I think what you are looking for is the following sequence:
2, 3, 13, 113, 103, 109, 1109, 1009, 1039, 2039, 2029, 2027, 2017, 2011, 2081.

Ha! That checks out, though I have no idea why my code missed it. Hilariously, in my OCD-like double-checking of every other result, I of course skipped over 2081 because I had confirmed that it couldn't be a relative. >_< Good to know that I'm not going crazy, and that it was just the usual careless oversight. I know there's no way my initial approach would scale to 10⁷ anyway though, so I'm going to start from scratch with a more clever approach. Anyway, much appreciated! I don't see a lot of recent activity on these forums so I was a little worried my question would drift unanswered into the endless archives of years-old forum posts.

EDIT: ...this is embarrassing, but I discovered the bug. Due to a sloppily-written while-loop, I was only substituting digits up to 8. So the check for paths from 2027 didn't catch 2029. Weirdly enough 2081 is the only one that was affected by the bug.

EDIT 2: Solved! Thank you again

[mdean]

Dumb question: is 2 a 2's relative?

[Georg]

Yes.

[m0nad]

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!

Would it be too much of a spoiler to suggest the last couple of digits of one of the primes where that "something" happens?
10**3 + 10**4 work OK here, I believe 10**5 is OK, too, I don't know about 10**6, and 10**7 does not work for me.

[pxor]

Hey, could anyone explain how is 503 connected to 2?

[jaap]

Hey, could anyone explain how is 503 connected to 2?

503 is connected to 103, and the rest is via the chain given as an example in the problem:
2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 503