50
13
The "prime ant" is an obstinate animal that navigates the integers and divides them until there are only primes left!
Initially, we have an infinite array A containing all the integers >= 2 : [2,3,4,5,6,.. ]
Let p
be the position of the ant on the array. Initially, p = 0
(array is 0-indexed)
Each turn, the ant will move as follows:
- if
A[p]
is prime, the ant moves to the next position :p ← p+1
- else, if
A[p]
is a composite number, letq
be its smaller divisor > 1. We divideA[p]
byq
, and we addq
toA[p-1]
. The ant moves to the previous position:p ← p-1
Here are the first moves for the ant:
2 3 4 5 6 7 8 9 ...
^
2 3 4 5 6 7 8 9 ...
^
2 3 4 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 7 3 7 8 9 ...
^
Your program should output the ant's position after n
moves. (you can assume n <= 10000
)
Test cases:
0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512
Edit. you can also use 1-indexed lists, it's acceptable to display the results 1, 7, 10, 275, 513 for the above test case.
This is code-golf, so the code with the shortest code in bytes wins.
32I honestly thought there was an ant on my screen when I saw this in the Hot Network Questions. – Kodos Johnson – 2017-10-09T06:09:20.927
14I wonder whether the sequence is well-defined for arbitrarily large
n
(or whether the composite case could ever push the ant to the left of the initial2
). – Martin Ender – 2017-10-09T06:59:49.310Can we use 1-indexing for the array instead? – Tom Carpenter – 2017-10-09T09:12:13.280
@Tom Yes, no problem, as long as your program returns the correct results. – Arnaud – 2017-10-09T09:17:23.780
1@SuperChafouin so outputs of for the test cases can be:
1,7,10,275,513
if 1-indexing stated? Or would they still need to match your outputs. – Tom Carpenter – 2017-10-09T09:22:30.923@SuperChafouin if we're using 1indexed array, is a 1-indexed result "correct"? – kamoroso94 – 2017-10-09T10:25:11.913
It's OK for me. I edit the question to allow 0-indexation or 1-indexation. – Arnaud – 2017-10-09T10:32:40.280
12@MartinEnder Another open question is whether a prime > 7 can eventually be left behind for good. – Arnauld – 2017-10-09T10:39:15.740
@Arnauld I'm curious how the ant's position grows with respect to the number of moves. My guess is logarithmic. – kamoroso94 – 2017-10-09T12:58:03.850
@kamoroso94 It's probably somehow related to ω(n) and/or Ω(n). If p is the position and n is the number of moves, then p seems to be in the order of magnitude of n.log(n)/log(log(n)). But that's a complete guess...
– Arnauld – 2017-10-09T16:05:00.563I have the Android widget for stack exchange...I thought there was a bug on my screen. – Evorlor – 2017-10-09T21:33:30.073
1@Arnauld Yeah, we can conjecture that for any given position
P≥0
there is anN≥0
(depending onP
) such that if the numbern
of moves is greater thanN
, then the positionf(n)
of the ant will always be greater thanP
, and the array entries with indices small thanP
will all be one-digit prime numbers (i.e. belong to{ 2, 3, 5, 7 }
). – Jeppe Stig Nielsen – 2017-10-10T14:23:45.393Looks oddly related to this mathematical sequence, wonder whether we could alter the projection to stop it diverging later on in the sequence:
– Alexander Craggs – 2017-10-10T15:18:06.923M(0)=0; M(n+1)=M(n).f(M(n), n).f(M(n), n+1).d(M(n), n); -f(m, n)
@KodosJohnson, gotta love outdoor computing! – NH. – 2017-10-10T19:47:43.880
2@Arnauld Out as far as move n = 1,000,000,000 (where p = 17156661), the relationship between n and p is very close to p = n/(ln(n)*ln(ln(n))) . – Penguino – 2017-10-12T03:17:53.397
1
I added this sequence to the On-Line Encylopedia of Integer Sequences as sequence A293689. The graph is worth looking at.
– Peter Kagey – 2017-10-19T04:39:08.013