All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Prime-Time Ant (Posted on 2010-10-05)
An ant is placed on a large sheet of graph paper on which numerous concentric squares have been marked in ink, indicating each successive odd prime starting with 3. The ant starts moving North, from the centre square of the 3x3 block, and will alternately;
1. Turn right when it reaches an ink line (which seems like a ‘wall’ to the ant); and
2. Resignedly clamber over the ‘wall’ and continue to scurry forwards in its current direction until confronted by another wall.

Hence the first few moves of the ant will be: North 1 step, turn right, East 2 steps, turn right, South 4 steps, turn right, West 7 steps, turn right, and so on.

Question: How many steps will the ant have had to take by the time it climbs over the 10,000th ‘wall’?

 No Solution Yet Submitted by broll No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer-aided solution | Comment 1 of 2

At any given stage of travel, past the first two such straight runs, the ant travels the distance based on the given prime number plus that based on the second previous prime. That is, for example, the first three primes that are used are 3, 5, 7 and 11. A "distance based on" is (p-1)/2, so the based distances away from the axes are 1, 2, 3 and 5 respectively (despite appearances, these are not always prime or 1).

So for example, the "south 4 steps" mentioned in the puzzle is the 3+1, and the "west 7 steps" is the 5+2.

`10   for Stp=1 to 1020    P=prm(Stp+1)30    Pprev=Prev:Prev=Dist:Dist=(P-1)//240    Steps=Dist+Pprev50    Tot=Tot+Steps60    print stp,Steps,Tot70   next`

calculates the first few runs as:

`run#   length   total so far 1       1       1 2       2       3 3       4       7 4       7       14 5       9       23 6       13      36 7       15      51 8       19      70 9       23      93 10      26      119 `

During run 1, the ant has not yet climbed a wall; only after run 2 has the ant climbed one wall. This lag by one must be kept in mind at the end.

Changing the program to

10   for Stp=1 to 10001
20    P=prm(Stp+1)
30    Pprev=Prev:Prev=Dist:Dist=(P-1)//2
40    Steps=Dist+Pprev
50    Tot=Tot+Steps
60    print Stp,Steps,Tot
70   next

results in the last few lines being:

` run#    length        total so far 9990    104663          495108407 9991    104669          495213076 9992    104679          495317755 9993    104686          495422441 9994    104691          495527132 9995    104699          495631831 9996    104705          495736536 9997    104711          495841247 9998    104716          495945963 9999    104722          496050685 10000   104732          496155417 10001   104743          496260160 `

So that after its 10001th run, it has climbed 10000 walls and taken 496,260,160 steps. But some of those steps were taken after having climbed over that 10,000th wall, upon reaching the 10,001st wall, but not yet ready to climb it--only diverting to the right. To backtrack to where the 10,000th wall was climbed we have to subtract the difference between the distance based on the 10,002nd prime and the distance based on the 10,001st prime. Those primes are 104759 and 104743, with respective axial distances of 52379 and 52371, which differ by 8, so at the 10,000th wall crossing the ant has traveled 496,260,160 - 8 = 496,260,152 steps.

We can codify what we did so as to verify that this is the correct procedure, by looking at the beginning of the tour:

10   for Stp=1 to 10
20    P=prm(Stp+1)
30    Pprev=Prev:Prev=Dist:Dist=(P-1)//2
40    Steps=Dist+Pprev
70   next

yielding adjusted totals in the rightmost column:

` 1       1       1       0 2       2       3       2 3       4       7       6 4       7       14      12 5       9       23      22 6       13      36      34 7       15      51      50 8       19      70      68 9       23      93      90 10      26      119     118 `

which can be verified by inspection of the diagram of the original few steps. Restoring the full number of steps, the resulting last few lines are:

` 9996    104705          495736536       495736534 9997    104711          495841247       495841244 9998    104716          495945963       495945960 9999    104722          496050685       496050682 10000   104732          496155417       496155410 10001   104743          496260160       496260152 `

verifying the figure found previously.

But actually, we need to add .5 to these steps as the and needs to go 1/2 step to get to the actual wall.

So the final answer becomes 496,260,152.5 steps, counting the wall-crossing square as being two half-steps.

Edited on October 6, 2010, 2:52 am
 Posted by Charlie on 2010-10-06 02:50:37

 Search: Search body:
Forums (0)