44
6
The "prime frog" is a strange animal that jumps between integers, until it arrives on 3 or 19...
Your program should accept an integer n
as input and output the result of the below algorithm (3
or 19
).
For a given integer n >= 2
:
- Let
f
be the position of the frog. It is initially set ton
- if
f = 3
orf = 19
: the frog stops jumping - halt the program and outputf
. - if
f
is prime : the frog jumps to the position2×f-1
. Go back to step 2. - if
f
is composite : letd
bef
's biggest prime divisor. The frog jumps to the positionf-d
. Go back to step 2.
Examples:
An example with n = 5
:
5 > 9 > 6 > 3 stop
The program should output 3
.
Another example with n = 23
:
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
Again, the program should output 3
.
Test cases:
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
You can assume 1 < n < 1000000
(I have checked the program ends for these values).
1A comment on why I've chosen 3 and 19 as stop criteria : once the frog arrives on one of these numbers, it starts to loop back after a few iterations. 3 and 19 form two distinct loops. It seems all integers eventually arrive to the 3 loop or the 19 loop. – Arnaud – 2017-10-19T07:53:56.567
33 loop is [3 5 9 6 3] and 19 loop is [19 37 73 145 116 87 58 29 57 38 19] – Arnaud – 2017-10-19T07:56:37.683
8Cool Collatz variation. – Arthur – 2017-10-19T08:27:18.437
I wonder whether there is a mathematical proof or something alike on the topic – Keyu Gan – 2017-10-19T08:43:27.963
@SuperChafouin I wonder if there's higher primes that fall into a loop. – kamoroso94 – 2017-10-19T08:46:56.433
2@kamoroso94 I haven't checked for bigger values. For n < 1000000, 62% of numbers return 3 and 38% return 19. – Arnaud – 2017-10-19T09:34:46.420
3If we cannot prove that the frog always comes to
3
or19
, we could change item 2. in the algorithm to say that if the frog has entered any loop (encountered a position it has seen before), then it ceases the jumping and returns the smallest member of that loop. – Jeppe Stig Nielsen – 2017-10-19T12:06:44.8901@Jeppe That was my original algorithm, it would stop whenever it entered a loop. As I noticed it was always the 3-loop or the 19-loop, I thought it would be funnier for golfing to add 3 and 19 as stop conditions. – Arnaud – 2017-10-19T12:55:48.540
@SuperChafouin what should the program do if reaches neither 3 nor 19? Or can we assume the input will? – PyRulez – 2017-10-19T16:55:26.137
4@PyRulez If it reaches that, you should probably tell the OP. – mbomb007 – 2017-10-19T16:59:32.743
3@KeyuGan Maybe this would be a good thing to post about on Math.SE. – mbomb007 – 2017-10-19T17:00:57.670
1Hold true for first 10^8 primes – Keyu Gan – 2017-10-19T20:21:15.403
@Abigail Absolutely! If there is a number that never loops, then the frog will tend towards positive infinity; however, I do not see how the frog could ever realize that this was the case, so I do not see how that would change the frog "rules". But it would still be very interesting if someone could prove that all frog sequences are bounded (the prime frog halting problem). – Jeppe Stig Nielsen – 2017-10-23T07:06:35.977
2please add link to math.se if someone posts it there. – bolov – 2017-10-23T10:42:03.450