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

Home > Numbers
Prime-Time Ant (Posted on 2010-10-05) Difficulty: 3 of 5
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.)
Solution 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 10
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

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
50    Tot=Tot+Steps:Adjusted=Tot-(Dist-Prev)
60    print Stp,Steps,Tot,Adjusted
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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information