Just a short tip on how to potentially solve this.
Take a close look at the given example number of 30.
All its divisors form a pair: 1 and 30, 2 and 15, 5 and 6, 3 and 10.
If the sum of each individual pair is prime, you found a prime generating integer:
1 + 30 = 31
2 + 15 = 17
5 + 6 = 11
3 + 10 = 13
All prime.
Which is exactly what the problem description states by giving you the formula d + n/d.
Problem 686 has a bit of a cryptic explanation:
Welcome to Project Euler’s Problem 59, a decryption challenge.
This is a sample of the encrypted text:
Hard to imagine that I have spent two and a half years with a data encryption company not having any idea on how to crack it?
Even more embarrassing, I posted the problem on my Instagram story and received a screenshot of the correct answer roughly two hours later by a friend who is still working professionally in the field of data security and endpoint protection.
So, how did I solve it? First on reading up on the basics of XOR decryption. Which I didn’t need at all in the end. But at least I did learn something new.
Let’s have a look at a very simple XOR encryption, as given in the problem’s description.
65 XOR 42 = 107. How comes?
ASCII 65 is a capital “A” or 1000001 in binary. 42 is an “*”. In binary it is represented by 0101010.
So…
1000001
0101010
XOR
1101011
The XOR-table (exclusive OR) is simple.
0 and 0 become 0.
0 and 1 become 1.
1 and 0 become 1.
1 and 1 become 0.
That’s all there is to know.
Therefore, 1000001 XOR 0101010 = 1101011 (107, “k”).
The good thing about modern programming languages like Java is that XOR is a built-in operator, ^.
For example 65 ^ 42 = 107. There is absolutely no need to shift any bits around.
Next, I did look up some decryption strategies online. Usually the key length is not known, and one has to figure it out first. Luckily, this is not the case for Problem 59. The key length of 3 is given. Also, the information that it consists of lower case characters only.
Once I understood what is meant by “the key is repeated cyclically throughout the message”, I divided the encrypted text into three blocks. Block one: blue. Block 2: red. Block 3: green.
Behause that’s how the text is encrypted, assuming that the key is “abc”:
For each block I found out which ASCII number occurs most often.
Next, I assumed that this number represents the most common letter in the English language, which is “e”.
A faulty assumption by the way. By reading a bit more about the problem, it occurred to me that the most common character in the text is not an “e” but actually a “SPACE”.
The rest was easy. I XORed each of the three numbers with a SPACE, which gave me three lower case characters.
Next, I pasted the encrypted text into an online tool and provided a guess of the key based on those three characters. The decryption process returned an English text instantaneously.
All that was left was to convert the resulting text back to ASCII codes and calculate their sum. Done!
This is another Project Euler challenge that I initially solved by try and error and some help from Dr. Google. A little Wikipedia research (German only) reveals the correct result without the necessity of writing any line of code.
Nevertheless, I tried to implement a solution. Currently, I am down to a one-minute runtime, which is way too slow. But it’s the best algorithm I could come up with at the moment. Therefore it is time to wrap up.
First, I implemented a function to retrieve all proper divisors of a given number and calculate their sum. This was one of the first areas of my code which I could optimize. Let’s take the number 12 for example. Its proper divisors are 1, 2, 3, 4, and 6. Instead of determining each divisor individually, a little trick can be applied. Once you know that 2 is a proper divisor of 12 you know immediately that the number 6 is a proper divisor as well. The same is true for 3, which pairs with 4. Only half the work to be done.
Now it was time to generate number chains. I chose to use a simple for-loop to kick off each chain, followed by a while-block to make it grow. But to what upper limit? The problem description states that no element of the list must exceed 1.000.000. It turns out that the first number that yields a sum of its proper divisors, which exceeds this limit is 327.600. To be on the safe side, I decided to set the upper limit to 350.000. As the solution to Problem 95 is a way smaller number my assumption seems to be faulty. But I lack the math skills to come up with a better idea.
Next, I did some research on potential chains. It looks like every chain “terminates” somehow.
Using a while-loop to grow each chain, what are the cases I will encounter?
Case 1: The chain terminates with 1.
Example: 10 → 8 → 7 → 1
Case 2: It’s a perfect number.
Example: 6 → 6
Case 3: It’s an amciable pair.
Example: 284 → 220 → 284
Case 4: It’s an amicable chain. That’s what I’m looking for.
Example: As stated in the problem description, 12496 → 14288 → 15472 → 14536 → 14264 → 12496
Case 5: It does not start as an amicable chain but turns into one.
Example: 562 → 284 → 220 → 284 (see Case 3)
I tried to optimize by keeping a list of “dead ends”. For example, once I know that 10 results in a useless chain, I store it. Whenever I come across 10 one more time, I can abort immediately. Over time my “dead ends” keep growing, and I can abort more and more chains. This comes with the cost of having to check this list.
That’s it. Create chains plus a couple of assertions.
Abort when discovering…
Store the longest chain and return its starting point as a solution to Problem 95.
As written above, my implementation has a runtime of roughly one minute. This is a strong indication that I must have missed something. But at the moment, I have no idea how to further improve my code. Now that I know the problem solution, I decreased the upper limit of my for-loop as a trial, which yields the correct result in a single second.
So, I might return to Problem 95 in the future.
This is Problem 51 “Prime digit replacements”:
The goal is to find the smallest member of a prime number family consisting of exactly eight primes that share one additional property.
With two examples given, the problem description is pretty clear. 56003, 56113, 56333…56**3. Replace the wildcards with the same digit and the resulting number is still prime.
Everything else is just vague as f***. How many wildcards? What’s their position? Will the “smallest” prime be a rather large number or not?
At least the wildcard values are more or less clear. As the prime number family will have eight members, eight different wildcard substitutes out of [0, 1, 2, …, 9] will be required.
Asking “Dr. Google”
Lazy as I am, I started googling for the term “prime number family”. For sure, there must be something on mathworld.wolfram.com. Mathematically illiterate as I am, I couldn’t find anything. Therefore, I had to go back to the drawing board.
DIY
Whenever I don’t know what to do, I tend to start with something very simple. In this case, a for-loop to generate numbers and a function to check for primes. With an upper limit of 1.000.000. Working on Project Euler problems often involves comically large numbers. Turns out this one time I got lucky with my uneducated guess.
I also just assumed (hoped) that the correct answer will contain only two or three wildcards. Nevertheless, I added a function to count the occurrences of a given digit within one of my prime numbers. Without paying any attention to its position.
Next, I added a replacement method. Beware of leading zeros!
And finally, a counter for the resulting primes after replacing the wildcards by iterating the list [0, 1, 2, …, 9].
After fiddling around with the parameters of my patchwork code and removing a couple of bugs, I found a promising small number matching the requirements, pasted it in the answer field, and hit jackpot faster than expected.
My solution might not be the most elegant, but it works and still executes reasonably fast (~1 second) after removing all guesswork from the code.
Before calling it a day, here are some hints in case you are stuck working on Problem 51:
Have fun!
Reading the description of Problem 86 gives me a headache. Every time I am convinced that I finally got it, I begin to drool, wee myself and have to start over. What an excellent premise for a new blog post.
This is Problem 86 in all its glory:
The first part is easy to understand. A happy little spider is put onto a cuboid and walks from corner S to corner F.
It is stated that, given the exact measurements of the cuboid, the length of the shortest possible path from point S to point F is 10. How’s that?
Back to elementary school where I learned how to build a paper die.
That’s how the given cuboid looks unfolded. By applying some basic math it is now easy to calculate the distance between S and F. As it is a straight line it is indeed the shortest route from S to F. It is also the hypotenuse h of a right-angled triangle. Therefore…
The distance between S and F does not have to be of integer value though. Just imagine a cuboid having slightly different measurements.
So far so good. Let’s continue. The part about “up to three shortest path candidates” can be simple ignored. Interesting but not necessary to solve this particular problem.
Back to calculating h.
And applied to the cuboid:
That’s the formula to get the shortest route h. Just remember that we are only interested in integer values of h. So we will need a check for that.
The cuboid is of volume a x b x c. It is safe to assume that all are of integer value as the problem description does not state otherwise. We can start with 1 for a, b and c, with a maximum value of M. For example we can have cuboids of volume 1 x 1 x 1, 1 x 1 x 2, 1 x 1 x 3 and so on up to M x M x M.
Each increase of a, b or c will result in a different cuboid. And for each of these cuboids (at least) one shortest route from S to F exists.
We now have to find the least value of M, where the total number of shortest routes exceeds 1.000.000.
Let’s suppose M = 1. That’s simple. We only have a single 1 x 1 x 1 cuboid. And only one solution for h, which is 2.23. This does not qualify as it is not of integer value. Our total count would be still 0.
Let’s suppose M = 2. What kind of cuboids can we build?
1 x 1 x 1: no integer solution for h
1 x 1 x 2: no integer solution for h
1 x 2 x 1: no integer solution for h
1 x 2 x 2: no integer solution for h
2 x 1 x 1: no integer solution for h
2 x 1 x 2: no integer solution for h
2 x 2 x 1: no integer solution for h
2 x 2 x 2: no integer solution for h
Still a total count of 0.
What might be not so obvious right away is that we have duplicates here. The problem description states that rotations can be ignored. So which ones are actually duplicates?
1 x 1 x 1: unique cuboid
1 x 1 x 2: first unique occurrence of cuboid
1 x 2 x 1: rotation of 1 x 1 x 2
1 x 2 x 2: first unique occurrence of cuboid
2 x 1 x 1: rotation of 1 x 1 x 2
2 x 1 x 2: rotation of 1 x 2 x 2
2 x 2 x 1: rotation of 1 x 2 x 2
2 x 2 x 2: unique cuboid
Note: Even though some cuboids are just a rotation of other cuboids the result for h will be different.
But in the end it’s actually just:
(a x b x c)
1 x 1 x 1
1 x 1 x 2
1 x 2 x 2
2 x 2 x 2
And that looks like a simple for-lop ranging from 1 to M = 2 where always a >= b >= c (or c <= b <= a).
Let’s increase M one more time to M = 3. When do we have the first integer solution for h? If I’m correct this would be 3 x 2 x 2.
Let’s sum it up. We have a simple formula to calculate h. We also know that we could use a simple for-loop to gradually increase the size of our cuboids. What else do we need? Definitely we need to keep count of the integer occurrences of h because we have to abort the creation of cuboids when we reach a certain limit. Namely 1.000.000.
And once we abort, we are only interested in the value of a. That’s all.
I refer from posting my source code here. But this should be explanation enough so you can start coding a solution yourself. Good luck and have fun!
I am currently working my way through Zed Shaw‘s book Learn C the Hard Way which I first heard about on Scott Hanselman’s fantastic podcast Hanselminutes.
Apparently there seems to be some controversy over Zed’s content and style of teaching. As I am here to learn and not to judge, especially on a topic I am far away from being an expert in, I couldn’t care less.
Exercise 4 “Using a Debugger” is a brief introduction to using GDB and LLDB. As the book only lists a quick reference card and the accompanying video is a bit of a mess, I decided to put my notes into writing. With the sole focus on LLDB as I am working on macOS.
To make full use of LLDB this tiny piece of code has to be compiled using the -g flag:
gcc -Wall -g ex3.c -o ex3
Now just launch LLDB with the executable as argument:
lldb ex3
(lldb) target create “ex3”
Current executable set to ‘ex3’ (x86_64).
Set a breakpoint in main and you are good to go:
(lldb) breakpoint set –name main
Breakpoint 1: where = ex3`main + 15 at ex3.c:5:7, address = 0x0000000100000f1f
Run your program:
(lldb) run
Process 23621 launched: ‘/Users/frededison/Learn C/ex3’ (x86_64)
Process 23621 stopped
* thread #1, queue = ‘com.apple.main-thread’, stop reason = breakpoint 1.1
frame #0: 0x0000000100000f1f ex3`main at ex3.c:5:7
2
3 int main()
4 {
-> 5 int age = 10;
6 int height = 72;
7
8 printf(“I am %d years old.\n”, age);
Target 0: (ex3) stopped.
Step forward into function calls:
(lldb) step
Or step over them:
(lldb) next
Print expressions. For example:
(lldb) print age
(int) $1 = 10
Quit when done debugging:
(lldb) quit
A full tutorial on using LLDB can be found here. For me the few commands listed above are enough to proceed to Exercise 5 of Zed’s book.
This post is going to be a pretty short one. Now that I have tasted blood again, I managed to “solve” another Project Euler problem just before hitting the hay last night. I’m still working on the supposed to be easy ones though.
I put “solved” in quotation marks due to the massive sledgehammer which I used for arriving at the solution…a simple for-loop. Does 1 satisfy the given definition? What about 2? And 3? Bang! Bang! Bang!
Using a dumb loop was the first thought that occurred to me on how I could solve this challenge and I didn’t get any smarter in the end.
I started by consulting Wolfram MathWorld to find out more about this numerical phenomenon. Just to discover Narcissistic Numbers. Which is NOT the solution to this given problem.
An n-digit number that is the sum of the nth powers of its digits is called an n-narcissistic number.
Below this definition MathWorld displays a nice little table of all the numbers that satisfy this definition up to n equals 39.
That was easy. For n equals 5 the numbers I was looking for are 54748, 92727, 93084.
Unfortunately…
These are not the numbers you’re looking for.
Obi -Wan Kenobi
Or to be a bit more precise, these are not the only numbers required to reach the target sum.
After several failed attempts to submit 240559 (54748 + 92727 + 93084) I came to the conclusion that most likely I am not smarter than Project Euler and started thinking about what I was missing here.
If you read the problem description carefully, it becomes clear that your search is not limited to n-narcissistic numbers only. For example 4150 is just fine as well:
4150: 45 + 15 + 55 + 05 = 4150.
The number doesn’t have to be precisely n-digits long. I hope this helps.
Now I have to read the forum posts as usual. And then move on to the next problem on my list, Coin sums.
Last year I made the decision to blog less about Project Euler problems. Especially to stop posting full blown solutions including source code. Still, I want to share interesting challenges and my attempts at solving them.
Number 28, Number spiral diagonals, falls into the category of problems I had to study at least three times just to understand what the description actually wanted to tell me. I’m pretty sure that I’m not the only human being on this planet scratching his head after reading the following lines for the first time:
Get it? No? Let me explain. Start with the number 1 in the center and then continue clockwise with the next number, 2. Just write it next to the first number. Continue with 3 and 4.
Keep going and you will have created a 3 x 3 spiral grid.
Add even more numbers…
Done. A 5 x 5 grid of spirally arranged numbers from 1 to 25. That’s all!
Now let’s have a look at all four diagonals.
Create the sum of all highlighted numbers: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25. The result is 101.
So far so good. But what about the sum of the diagonals of a 1001 x 1001 spiral grid? This is the actual challenge!
Warning: If you just wanted to understand the problem but prefer to figure it out all by yourself, stop reading now! No implementation details will be given, but enough information to spoil all the fun for you.
My first approach was to simply use Excel. Without any coding at all. Just to get the number and to see how big it actually is. But after approximately two dull minutes of typing numbers into a spreadsheet I threw in the towel. Trying to create such a huge spiral manually is just plain dump. Stupid me.
Then I started banging my head against the wall trying to figure out how to create such a grid programatically. Should I use a list of lists? But how to continue? Therefore back to the drawing board.
I started paying closer attention to the properties of the given 5 x 5 spiral grid. Obviously you start with the 1 in the center. This number is part of every diagonal. It will be counted only once. Therefore the solution most likely looks similar to this highly sophisticated snippet of code: int result = 1 + foo;
First, I tried to reduce the challenge to the smallest possible spiral, a 3 x 3 grid. The numbers located along the diagonals are 3, 5, 7, 9.
Back to the 5 x 5 version: 13, 17, 21, 25.
Next, I created a 7 x 7 spiral on paper. The new diagonal numbers are 31, 37, 43 and 49.
Observation 1: It doesn’t matter how big the spiral gets, for every layer only four numbers are of interest, the corner numbers that are part of the diagonal.
Which is kind of obvious.
Observation 2: The numbers of interest follow a pattern.
3 x 3 spiral: The next relevant number is the current number + 2.
5 x 5 spiral: The next relevant number is the current number + 4.
7 x 7 spiral: The next relevant number is the current number + 6.
For every additional grid layer the gap between these numbers increases by 2 (2, 4, 6…).
But how to continue from here? That’s not enough to implement a solution yet. What happens after I complete the first 3 x 3 spiral. The last number I need to consider is 9? The first number of interest of the 5 x 5 layer is 13. For the 7 x 7 layer it will be 31.
First numbers of each layer: 3, 13, 31…
Last numbers of each layer: 9, 25, 49…
What if I combine these numbers? Because that’s what I actually need. Based on my second observation I can easily compute the missing numbers for each layer, but I need a starting point.
9 → 13: A difference of 4.
25 → 31: A differente of 6.
49 → 57: A difference of 8.
81 → 91: A difference of 10.
Observation 3: I am able to compute the first relevant number of each layer based on the last number of the previous layer. The gap between these numbers increases by 2 as well. I need to keep count of the layers though.
And this should actually be enough to implement a working solution.
Unfortunately the third observation just occurred to me while typing these lines. While playing with pen and paper I just didn’t see it. But I still solved the challenge using a fourth observation.
I added a few additional layers to my 7 x 7 spiral grid…
…with the focus on potential patterns inherited in the diagonals. Let’s have a look at the top left one: (1), 7, 21, 43, 73, 111…
And that’s what I noticed:
7 → 21: 14 (initial gap)
21 → 43: 22 (14 + 8)
43 → 73: 30 (22 + 8)
73 → 111: 38 (30 + 8)
And this pattern is true for each and every diagonal.
Observation 4: Every diagonal follows the same pattern. The first step from the 3 x 3 to the 5 x5 layer is unique for each diagonal but then the current gap is always the previous gap + 8.
And that’s the observation I used for coding my solution.
So far I didn’t have a look at the Project Euler forum. But I’m pretty sure the spiral numbers challenge holds far more secrets than I could figure out by myself.
I took quite a leave of absence from my little dev blog. The fun thing is that I actually got a hell lot of coding done in the meantime. I completed a couple of Project Euler challenges and was very active on freeCodeCamp where I stumbled through 330 lessons, scripting tasks and full blown projects so far. After achieving the camp’s Front End Development Certification as well as its Data Visualization Certification I left CodePen for good and moved on to GitHub and Glitch, “the friendly community where you’ll build the app of your dreams”, to work on API projects like a timestamp microservice or an URL shortener. Ah, and I was fighting some Flexbox Zombies and joined Wes Bos’ fantastic JavaScript30 online course. Not to forget my full time gig as a developer and project lead in the telco industry. Meaning that I have a lot of unwritten posts in my queue.
I actually stopped blogging more than half a year ago when I threw in the towel trying to understand a fellow Project Eulerian’s solution to this amicable numbers problem. But now it’s finally time to finish what I started.
As this is already the fifth post on amicable numbers you can get the full story here, here, here and here.
The following quote…
In fact this can be even improved on using the prime factorisation of n.
If we know the prime factorisation if n it is easy to calculate the sum of the divisors of n from that.
…pointed my attention to an article on mathschallenge.net about working out the sum of divisors. This is when my monkey brain gave in.
The part I just couldn’t figure out was the line starting with “Hence…” until it finally made click a couple of days ago. And it is so simple that I’m still angry about my own stupidity and giving up so easily.
This part is obvious:
Looking at the left-hand side of the equation, all I have to do is to factor out σ(pa) and divide by (p−1). That’s it. Struck by blindness.
mathchallenge doesn’t provide a proof, which I would not have understood anyway, but gives a sample calculation instead:
I now have a handy formula to calculate the sum of divisors but I am still working with powers of prime numbers only. What about the sum of divisors of a non-prime e.g. 72?
[…] the usefulness of the function, σ(n), is its multiplicativity, which means that σ(a×b×…)=σ(a)×σ(b)×…, where a, b, …, are relatively prime.
mathchallenge’s example:
I see, all I have to do is to factorize a number until I remain solely with factors, which itself are relatively prime.
How can this be used to further improve my code? This is the sample solution provided by the Eulerian hk, which I translated to a bit more verbose Java code.
What am I doing here? A dry-run of this algorithm is pretty boring. So I will stick to one sample run using 72 as input number, as I already know the result, which should be 195.
Therefore I start with 72 as num, 1 as sum and 2 as p.
First let’s see if 2 times 2 is less or equal to num or num greater than 1. This prevents me from checking prime factors greater than num itself and of course I have to terminate my while-loop somehow.
Now, I check if 72 can be divided by p without remainder. As 72 % 2 == 0 is true I will continue.
I introduce a variable j and give it the value of 2 times 2 equals 4. And I divide 72 by 36, which is my new value for num.
As long as num can be divided by p without remainder I will be stuck in the inner while-loop. 36 % 2 == 0 → true, 18 % 2 == 0 → true, 9 % 2 == 0 → false. I am out of here. Meanwhile j got increased to 16.
I am now able to calculate the first part of the sum. This is where the formula shown above comes in. 1 * (16 – 1) / (2 – 1) = 15.
Having the number 2 factored out, I will continue with 3 as new value for p.
Note that num is now only 9. But we are still caught in the outer while-loop, as 3 times 3 equals 9, which is less or equal to 9 and greater than 1.
Because 9 can be divided by 3 without remainder, we calculate a new value for j, which is 3 times 3 equals 9. num becomes 9 / 3 = 3 and we enter the inner while-loop again.
j turns into 27.
15 * (27 – 1) / (3 – 1) = 195.
And now we are out of the outer while-loop.
The line if (num > 1) {sum=sum * (num + 1);} only covers the case that one prime factor greater than num remains. This is not the case this time as num got reduced to 1.
Finally done! Party time, excellent!
I guess this will be my last post about Project Euler problems. I just had to finish this. Remember “Always be closing”. But I highly doubt the usefulness of posts like this one. (A) It’s very unlikely that anyone who is smart enough to figure this stuff out will actually read my blog. (B) I’m just a stupid guy trying to get better at what I do. There are already way better resources available online. I know, ’cause I used them myself. (C) I really should respect Project Euler’s advice:
[…] It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.
spank the codemonkey 