20120602, 04:31  #1 
Jun 2012
1 Posts 
Project Euler
Hi
I find 384 to be a tough one. In the sense that I get a system overflow error when I create an array to store the s(n) values. Can anyone suggest a better approach? Thanks. 
20120603, 05:06  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Round these parts, you're not likely to get an answer for such a question. You might get an answer if you post what you think might be a viable alternative. (I'd help you myself, but I'm not yet up to snuff on such mathematical things.)

20120603, 10:57  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×5×17×37 Posts 
The worst challenge for 387 was to wait until 3am for it to show up and then hack something fast with eyes already shutting involuntarily.
#39, even then. 
20120603, 20:30  #4 
Jun 2008
48_{16} Posts 
Believe it or not, I made the #1 spot years ago on (back then) mathschallenge.net. Then, there were only ~110 problems and I could handle the competition at a particular problem, probably because they were all asleep like you Batalov ;). Now the competition is much much heavier and I'm afraid this new #1 badge is out of my league...

20120603, 20:42  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·5·17·37 Posts 
They cleverly shift the posting times (and they should  to level the playing field; fair is fair). Too bad that sometimes (not this time) their site freezes after (or even before?) posting.

20120901, 22:02  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·5·17·37 Posts 
PE 392 is the first one after the summer break!
(already solved by 46) 
20120908, 16:10  #7  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
24DB_{16} Posts 
Was anyone able to screenshot the formulation of PE 393?
(the site is down, the users are down ) EDIT: there are signs of life: an empty page with the project banners came up... reloading... there it is. Quote:
Last fiddled with by Batalov on 20120908 at 16:36 

20120909, 17:46  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
For my solutions I find it easiest to think in loops multiplying by 2^n to account for direction with n being the number of loops.
2x2 has 2 solutions. Both effectively a loop with 2 directions. 2x3 has 2 solutions. Both are again loops around the outside with 2 directions. 2x4 can be: (1 2x4 loop) *2 because of 2 directions. (2 2x2 loops) * 4 because of 2 directions. 2x4 has 6 solutions total. 3x3 is impossible. 3x4 can be: (2 2x3 loops) *4 because of direction of movement (1 loop, 2 2x3 loops joined at one end) *4 because of 2 sides and 2 directions 3x4 has 8 solutions total. 4x4 can be: (4 2x2 loops) *2^4=16 because of 4 loops each having 2 directions (3 loops, a 2x4 loop on one side and 2 2x2 loops) * 32 because of 4 arrangements (2 2x4 loops) *8 because of 2 directions and 2 arrangements. (2 loops, 1 around the outside of the 4x4 and 1 2x2 loop in the centre) * 4 because of 2 directions (2 loops, a 2x2 in a corner and a L shaped loop) *16 because of 4 arrangements and 2 directions. (1 loop, 2 2x4 loops joined at one end forming a U) *8 because of 4 arrangements and 2 directions. (1 loop, 2 2x4 loops joined in the middle forming a H) * 4 because of 2 arrangements and 2 directions. It is possible to divide the 4x4 into 2 2x4s and use that for 56 of the solutions but you get 16 extra solutions because of duplicates when the 2x4s are reduced to 2x2 loops. 16+32+8+4+16+8+4=88 solutions total. 3x3 is certainly impossible as it forms an unbreakable chain around the outside. Is any area with an odd number of squares impossible? Can anyone prove it? 
20120910, 13:01  #9 
Sep 2012
2 Posts 
Hai i just dropped in, had troubles with this one as well, still have. But i couldnt leave this page without giving some proof.
For the an informal proof of the above: a grid graph is bipartite, since we can split up diagonals. Look at this 5x5 graph to tell a bit why If we want to make cycles in this, every 1 needs to go to a 1 and every 1 to a 1. So if we start a cycle in a 1, then closing a loop always takes an even amount of turns. same for cycles starting at a 1 square. What can we say about this, well if both sides are uneven, we can do two things: 1) make a cycle that fills the whole grid, but this isnt possible, since a cycle needs to have an even amount of squares 2) make a small cycle inside it and then move on making more cycles with the remaining squares. But since cycles are always even, we get that the remaining squares are still uneven. So if we keep doing this for a certain amount of times. we can never get the uneven part filled with a full cycle since cycles must be even. So thereby a square having 2 unequal sides gives 0 as outcome. And also to make it more general, its for every unequal numbered grid. But yea i now have a method to calculate f(6), but i dont really get it fast enough for f(8) and f(10) those numbers will be huge. 
20120911, 13:43  #10 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·17·139 Posts 
Your matrix is 4x5 (for which there are solutions). But we got the idea. This problem seems not complicate to be solved recursively.

20120911, 14:03  #11 
Sep 2012
2 Posts 
Oh yea oops, 4x5 indeed, but yea its about the idea of the proof ;D. And I have a recursive algorithm, but it already takes a few minutes for f(6). I guess i just missed something crucial in my algorithm. Have tried other methods, but no success in those at all.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Project Euler 486  lavalamp  Puzzles  8  20150204 14:28 
Project Euler #372  lavalamp  Puzzles  165  20120524 16:40 
Euler (6,2,5) details.  Death  Math  10  20110803 13:49 
Project Euler  MiniGeek  Lounge  2  20091023 17:19 
Bernoulli and Euler numbers (Sam Wagstaff project)  fivemack  Factoring  4  20080224 00:39 