### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 1691: Factory part… | |

Jim Randell on Puzzle 52: Football on the Isl… | |

geoffrounce on Enigma 1691: Factory part… | |

Hugh Casement on Enigma 1070: Time to work | |

Jim Randell on Enigma 1070: Time to work |

### Archives

### Categories

- article (11)
- enigma (1,157)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,808 hits

Advertisements

This Python program counts the number of squares crossed by the diagonal in an arbitrary grid, and looks for the first set of rectangles with the same area that provide N different ways of achieving the same number. It solves the N=3 case in 352ms.

Solution:(1) the area of the rectangles is 144 squares; (2) the diagonals pass through 24 squares.The dimensions of the three rectangles are 24×6, 18×8 and 16×9, as shown below:

The N=4 case requires rectangles with an area of 3024 squares (36×84, 42×72, 48×63, 54×56), with the diagonals each passing through 108 squares.

The N=5 case requires rectangles with an area of 3600 squares (30×120, 40×90, 45×80, 48×75, 50×72), with the diagonals each passing through 120 squares.

The N=6 case requires rectangles with an area of 32400 squares (90×360, 120×270, 135×240, 144×225, 150×216, 162×200), with the diagonals passing through 360 squares.

The N=7 case requires rectangles with an area of 129600 squares (180×720, 240×540, 270×480, 288×450, 300×432, 320×405, 324×400), with the diagonals passing through 720 squares.

After that my program takes too long to run.

Here is my Mma Code

It finds N=8 in 39 seconds, with 176400 squares and these rectangles, the format is

{a x b, GCD[a , b],No Squares cut}

{210 x 840, 210, 840}

{280 x 630, 70, 840}

{315 x 560, 35, 840}

{336 x 525, 21, 840}

{350 x 504, 14, 840}

{360 x 490, 10, 840}

{392 x 450, 2, 840}

{400 x 441, 1, 840}

There is a quick way to check how many squares are cut, it is a + b – gcd[a,b] where a and b are the size of the rectangle. To look for the various N change the [Max[f]==3 to 4 etc.

Paul.

p.s. the GCD[a , b] is 1 more than the number of nodes the line passes through.

Thanks. Using the computed formula

measure(a, b) = a + b - gcd(a, b)makes my program much faster than constructively counting the squares that the diagonal passes through.