Problem 068

[gaka]

I'm sure that i'm missing something realy tyni (or extreamly important part) but isnt 9411013635752824 supposed to be the correct answer?

Code: Select all

9411013635752824:

9+4+1=14
10+1+3=14
6+3+5=14
7+5+2=14
8+2+4=14

I just dont see why is this number wrong?

[GenePeer]

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely.

9 is not the numerically lowest external node.

[gaka]

Ohh yes.. I missed that part.

[suppurax]

[[8, 9, 9], [9, 9, 8], [10, 8, 8], [9, 8, 9], [8, 9, 9]] should be a solution:

all lists add to 26, and 8 is a minimum external node.

Is there an implicit rule I missed, pls?

[harryh]

Magic 5-gon's (just like magic 3-gon's, magic squares etc) use each number once.
Problem 68 (View Problem) states:

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings.

So, yes, it is implicitly assumed that each of the numbers 1 to 10 will be used only once.

[suppurax]

thx, problem solved now that I have the right input ^^

[BostonBear]

Because I'm a newcomer to Project Euler, I often find situations where I solve a problem and am unable to post to the forum thats granted access to problems solvers because they are already archived. Frankly I don't care for the locking down of the old archives because it assumes all insight that could possibly be gained has been posted. In problem 68 I find this is particularly not true. though I'm new to Python (ex Foxpro guy) and my code is often clunky, the algorithm I wrote solved the problem in 1.67 ms (on an old clunky macbook at that), which as far as I can tell is the fast solving of any code posted on there. The shortest code often took the longest time, so shorter might be cute, or have a certain cool/wow factor, but its not necessarily the fastest solution. I've found a few problems on here where I could do them on a calculator like the n/Phi(n) problem. but I always write a program to find the solution. The reason I expressed my displeasure on Problem 68 is that NOBODY seemed to realize some of the fascinating aspects of the 5-Gon solutions that were generated beside the one that was the proper answer. I won't give any information that makes it easier to solve for newbies, but I think SOMEBODY should have noticed a couple things. First, If you drew a number connecting the numbers of magic 5=gons (any of them , including ones with 10 in the inner ring), you get a 5 pointed star! I found that AMAZING! A bit of witchery in an Euler problem.. I tested many of the magic 5 gons and all had this proberty. The 2d thing that was amazing was if you drew a line connecting the outer ring numbers in numerical order you got a pentagram! That was SO cool! This is not a trivial observation, those lines could have easily bisected the inner star and never did. how could nobody else notice that? None of this information will help you find the solution and I didn't use that information in my code, it just popped out after I ran the program in *full mode* instead of *fast mode* so I could look at all the solutions for the different total number of digits (4 different totals in 5-gons). I actually got pen and paper then and drew some of the magic 5-gons, sloppily I might add. These really are *magic* numbers. and the final solution is the most magic of all considering the lucky number that popped out of it. I am surprised this isn't in the Quadrivium, or maybe it is, I haven't read the whoel book yet. I hope I'm not violating any protocol, and if I am , just delete the post, but my real point is that sometimes there are things to be gained from these problems that go BEYOND simply finding the solution or printing the shortest code. Plumbing the depths of the solutions AND, furthermore the *possible solutions*, can reveal fascinating insights.

BostonBear

[Hibernatus34]

Hello,

I didn't read the whole post, i stopped at 1.67 ms.
Just to let you know, i get 7.57 µs (ie. 0.0076 ms), and i don't think i've done anything special, i use a recursive algorithm IIRC.
Edit: I've read your post now, and it is interesting indeed. I didn't notice any of those properties. Thanks. These could inspire a few optimizations

But i too feel somewhat frustrated sometimes because i arrive 7 years after the battle. For example in problem 31 most people used a very bad algorithm, but fortunately problems 76 and 77 require the better one. 76 took me a few minutes to adapt my code made for 31, then a few microseconds to execute (15 µs).

[rayfil]

Please do not start a new topic when one already exists.

[BostonBear]

Hello,

I didn't read the whole post, i stopped at 1.67 ms.
Just to let you know, i get 7.57 µs (ie. 0.0076 ms), and i don't think i've done anything special, i use a recursive algorithm IIRC.
Edit: I've read your post now, and it is interesting indeed. I didn't notice any of those properties. Thanks. These could inspire a few optimizations

But i too feel somewhat frustrated sometimes because i arrive 7 years after the battle. For example in problem 31 most people used a very bad algorithm, but fortunately problems 76 and 77 require the better one. 76 took me a few minutes to adapt my code made for 31, then a few microseconds to execute (15 µs).

7.57 µs ??!! wow, what kind of machine are you running? I wrote this code in python

from time import time
st=time()
print "Process time is ", time()-st

and it took me 30.04 µs. thats right, this mac, running JUST one import statement, 2 time() calls and a print statement took 4 times longer than yours took to do the whole solution. I don't see anybody on here running times in microseconds. so you must be running a seriously suped up PC or mainframe.. its like comparing apples to oranges.. or you are running assember/C++ maybe?

[Hibernatus34]

7.57 µs ??!! wow, what kind of machine are you running? I wrote this code in python

from time import time
st=time()
print "Process time is ", time()-st

and it took me 30.04 µs. thats right, this mac, running JUST one import statement, 2 time() calls and a print statement took 4 times longer than yours took to do the whole solution. I don't see anybody on here running times in microseconds. so you must be running a seriously suped up PC or mainframe.. its like comparing apples to oranges.. or you are running assember/C++ maybe?

Hello,

I use C++ (MS Visual C++ 2010) on a fast processor : either Core 2 Duo E8400 or Core i5 2400.
I decided not to use parallel computing or SSE instructions, as it is too easy to divide processing time by 4 or more sometimes, and i'd better not spend any time in low level optimization, as i've got 256 problems left to solve
I use performance counters to measure times (resolution : 3 GHz for the E8400, 3 MHz for the core i5).
My functions return integers when suitable, so i don't count the conversion to a string and the console output.

For example, i've recently solved 81, 82, 83, and they all take 1 to 1.5 ms, among which 1 ms is spent loading input data. I've measured 55 µs for the algorithm itself in 82 and it is not low-level optimized at all.

I don't understand why so many C++ developers say they had to use Python instead of C++, while C++ is perfectly suitable for solving PE problems (big ints are easy to code, and rarely needed).

If you think my programs are fast, look at assembler solutions on the problems threads I think it was rayfil who impressed me several times with short and incredibly fast code.

[GenePeer]

1.67ms in Python is probably equivalent with the 7µs in C++. Python is an interpreted language which makes it inherently slow! This is very clear with problems like #153, where my Java code violated the 1 minute rule with 75s, while an exactly the same solution by another user in C++ takes 15s. This implementation in Python could take nearly 3min.

PS: That Java Code wasn't optimal, using info from the thread I was able to reduce it to 11s!

[mescher]

From wikipedia I understand a node to have 1 or 0 parents and an external node to be a node with 0 children.
According to the example in Problem 068, set 4,3,2; 6,2,1; 5,1,3 reading top-down,has external nodes 5,2 and 6. 2 being the least of these. Therefore, when you work clockwise you get the set above as described. Ok, I think that makes sense.

What is wrong then, with the set for a 3-gon ring 6,3,1; 4,1,5; 2,5,3. Which is a rotation of the second solution summing to ten. Doesn't it have external nodes 2,1,4? 1 being the least of these? wouldn't 631415253 be a bigger concatenation of digits?

Feel free to point me to a good resource on graph theory because I have absolutely no background in that subject. Thanks!

[thundre]

What is wrong then, with the set for a 3-gon ring 6,3,1; 4,1,5; 2,5,3. Which is a rotation of the second solution summing to ten. Doesn't it have external nodes 2,1,4? 1 being the least of these? wouldn't 631415253 be a bigger concatenation of digits?

The problem states "starting from the group of three with the numerically lowest external node". So if you're describing that ring, you have to start with 2.

Don't think of this object as a graph. The physical locations of the "nodes" are important, unlike graph-theory graphs. There is no notion of a straight line in graph theory, but here you must add totals which are on straight lines. The external nodes in this problem are the nodes with only one connection to another node. They are external to the "ring" (which, likewise, has nothing to do with ring-theory rings).

[tijko]

[link]http://projecteuler.net/problem=68[/link]

Hello, I've been reading and re-reading problem 68. I still do not understand how euler would like us to come up with the sets.

I understand that each number has to be used at least once. I understand that the leading set has to be lowest in each node level.

Other than this I am not seeing how to order the sets.

[thundre]

[link]http://projecteuler.net/problem=68[/link]

Hello, I've been reading and re-reading problem 68. I still do not understand how euler would like us to come up with the sets.

I understand that each number has to be used at least once. I understand that the leading set has to be lowest in each node level.

Other than this I am not seeing how to order the sets.

Clockwise.

In other words, if your first triple is (a,b,c), the second one is going to be the one with c as its middle element -- say (d,c,e). Then the next one will be the one with e as its middle element, and so on. The last triple will have b as its last element.

[tijko]

Hello Thundre,

Thanks for the reply, I didn't see that before thank you.

Another thing though, why wouldn't the first set instead of:

9 4,2,3; 5,3,1; 6,1,2
9 4,3,2; 6,2,1; 5,1,3

be:

9 2,4,3; 5,3,1; 6,1,2

[TripleM]

That isn't a valid solution at all - according to the first digits in each of your triples, you are putting 2, 5 and 6 on the outside, but then you have listed 2 as one of the inside numbers in the last triple.

I think you're really over-thinking this. Once you've filled in the grid, find the smallest outer number. Write that line from outside to in; write the next line clockwise from outside to in; write the next line clockwise from outside to in.

[tijko]

Problem 68 (View Problem)

I am was wondering if in the final '16 digit' string would 10 be counted as 1 '10' digit or 2 '1','0'?

Edit:

I got the correct answer and 10 was counted as two digits.

Thanks for all who help explain the question!

[msg6700]

hello every one.
can anyone explain why "5 1 3 4 3 2 6 2 1" isn't true in "magic" 3-gon ring ??