# The prime frog 🐸

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:

1. Let f be the position of the frog. It is initially set to n
2. if f = 3 or f = 19 : the frog stops jumping - halt the program and output f.
3. if f is prime : the frog jumps to the position 2×f-1. Go back to step 2.
4. if f is composite : let d be f's biggest prime divisor. The frog jumps to the position f-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).

• 3 loop is [3 5 9 6 3] and 19 loop is [19 37 73 145 116 87 58 29 57 38 19] – Arnaud Oct 19 '17 at 7:56
• Cool Collatz variation. – Arthur Oct 19 '17 at 8:27
• If we cannot prove that the frog always comes to 3 or 19, 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 Oct 19 '17 at 12:06
• @PyRulez If it reaches that, you should probably tell the OP. – mbomb007 Oct 19 '17 at 16:59
• @KeyuGan Maybe this would be a good thing to post about on Math.SE. – mbomb007 Oct 19 '17 at 17:00

# Python 2, 1019392908887 85 bytes

import sympy
n=input()
while~16&n-3:m=max(sympy.factorint(n));n-=[1-n,m][m<n]
print n


Try it online!

• while~16&n!=3 saves a byte. – Lynn Oct 19 '17 at 10:54
• Oh, ~16&n-3 even works! – Lynn Oct 19 '17 at 11:00

# C (gcc),  87  65 bytes

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);n=~16&n-3?f(n-k?:n+n-1):n;}


Try it online!

Explanation:

i,k;
f(n)
{
for (i=n; i>1;)              // Loop until k is prime (the largest positive
// i inequal to k that divides k is 1).
for (k=i; k%--i;);       // Find the largest factor k

n =                          // Returning like this is undefined behaviour,
// but happens to work with gcc. This can be
// replaced with return at the cost of 4 bytes.

~16&n-3                  // If n is 3 or 19, this expression equals 0 and
// the algorithm halts. Otherwise the function
// calls itself to perform the next iteration.

? f(n-k ?: n+n-1)        // If n-k is non-zero, n is not prime.
// In this case call f with the value of n-k.
// (Omitting the second n-k between ? and :
// is a gcc extension)
// Otherwise call f with 2*n-1.

: n;                     // All done, n is returned.
}


Portable version (72 bytes):

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);return~16&n-3?f(n-k?n-k:n+n-1):n;}


Try it online!

With more appropriate variable names:

f,r;o(g){for(f=g;f>1;)for(r=f;r%--f;);g=~16&g-3?o(g-r?:g+g-1):g;}


Try it online!

• Totally love the play with the word frog and your variables. +1. – rayryeng - Reinstate Monica Oct 20 '17 at 2:19

## Retina, 63 62 bytes

Thanks to Neil for saving 1 byte.

{^(11+)(?<!^\2+(11+))(?=\1+$) ^(?!(11+)\1+$|111$|1{19}$)1
$_  Try it online! Input and output in unary (the test suite uses decimal for convenience). This solution gets incredibly slow for larger inputs. The 9983 test case times out on TIO. ### Explanation Due to the {, both stages of the program are simply run in a loop until they no longer affect the string. We alternate between a stage processing composites and a stage processing primes. That lets us avoid an actual conditional (which doesn't really exist in Retina). If the current value is the wrong kind for the stage, the stage simply does nothing. ^(11+)(?<!^\2+(11+))(?=\1+$)



This processes composites. We match a potential divisor with (11+), but then we check that it's not composite with (?<!^\2+(11+)), so we only consider prime factors. Due to the greediness of +, this prioritise the largest factor. Then we check that this potential divisor is an actual divisor by trying to match the rest of the string with repetitions of it, (?=\1+$). This divisor is simply removed from the string, which is how you subtract something in unary. ^(?!(11+)\1+$|111$|1{19}$)1
$_  This processes primes, except 3 and 19. The negative lookahead makes sure that the input is not composite, not 3 and not 19. Then we match a single 1 and replace it with the entire string. This is a unary form of computing n - 1 + n, which of course is 2n-1. Once we hit 3 or 19, neither stage can match the string and it will no longer be changed. • Isn't 1$' the same as $_? – Neil Oct 19 '17 at 9:06 • @Neil Yes...... – Martin Ender Oct 19 '17 at 9:08 # Husk, 15 bytes Ω€p57§|o←DṠ-o→p  Try it online! ## Explanation Ω€p57§|o←DṠ-o→p Implicit input n. Ω Do this to n until €p57 you get a prime factor of 57 (which are 3 and 19): o→p Take last element of the prime factors of n Ṡ- and subtract it from n, §| or if this gives 0 (so n is prime), o←D double and decrement n.  # Jelly, 12 bytes _ÆfṂoḤ’$µÐḶṂ


Try it online!

### How it works

_ÆfṂoḤ’$µÐḶṂ Maink link. Argument: n µ Combine the links to the left into a chain. ÐḶ Repeatedly call the chain monadically until the results are no longer unique. Yield the loop, i.e., the first occurrence of the first repeated integer, up to and excluding the repetition. Let's call the argument of the chain k. _Æf Subtract all prime factors of k from k. Ṃ Take the minimum of the differences. This yields 0 iff k is prime. Ḥ’$        Compute 2k-1.
o           Take the logical OR of the results.
The result is now a rotation of either [3, 5, 9, 6] or
[19, 37, 73, 145, 116, 87, 58, 29, 57, 38].
Ṃ   Take the minimum, yielding either 3 or 19.


# Wolfram Language (Mathematica), 65 6668 bytes

#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&

• -1 bytes, thanks to Misha Lavrov!
• -2 bytes, thanks to Martin!

Try it online!

Inspired by the tip. Basically, it just recreates the algorithm.

//. is RepeatedReplace and /; is Condition. So, the code will replace i_ (a single quantity) with If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i], until i!=3&&!=19 evaluates True.

Benchmark:

• fun fact: this code would not work for larger numbers like 10000000010 because maximum number of iterations is 2^16 (= 65536) – J42161217 Oct 19 '17 at 20:27
• A slightly shorter way to check for 3 and 19 is #//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]& – Misha Lavrov Oct 20 '17 at 16:44
• @MishaLavrov but the result is incorrect? – Keyu Gan Oct 23 '17 at 0:08
• @KeyuGan For me, the two functions give exactly the same result for integers 1 through 1000. – Misha Lavrov Oct 23 '17 at 0:52
• Possibly the issue you're having is unprintable characters inserted when you copy and paste from the comments, which sometimes happens. – Misha Lavrov Oct 23 '17 at 0:55

# 05AB1E, 1918 17 bytes

[ÐƵηfså#pi·<ëDfθ-


Try it online!

Explanation

[      #            # loop until
Ð   så             # a copy of the current value is contained in
Ƶηf               # the unique prime factors of 171
pi          # if the current value is prime
·<        # double and decrement
ë   -   # else subtract
Dfθ    # the largest prime factor of a copy of the current value

• +1 for having an actual frog in your source code <ë – Arnaud Oct 19 '17 at 9:26
• For 57991 more than 1 minute – RosLuP Oct 20 '17 at 6:38
• @RosLuP: You're better off running very long test cases offline ;) – Emigna Oct 20 '17 at 7:16

# JavaScript (ES6), 7371 69 bytes

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38


### Test cases

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38

console.log('10   -> ' + f(10))   // 3
console.log('74   -> ' + f(74))   // 19
console.log('94   -> ' + f(94))   // 3
console.log('417  -> ' + f(417))  // 3
console.log('991  -> ' + f(991))  // 19
console.log('9983 -> ' + f(9983)) // 19

### Formatted and commented

f = n =>                 // given n
57 % n ?               // if n is neither 3, 19 or 57 (and assuming that n is > 1):
f(                   //   do a recursive call to f() with:
n -                //     n minus
(g = (k, d = 1) => //     the result of the recursive function g():
++d < k ?        //       increment d; if d is less than k:
k % d ?        //         if d is not a divisor of k:
g(k, d)      //           recursive call to g() with k and d unchanged
:              //         else:
g(k / d)     //           recursive call to g() with k = k / d, d = 1
:                //       else, d is now the highest prime divisor of n:
d < n ?        //         if d is less than n:
d            //           n is composite: return d, which results in f(n - d)
:              //         else:
1 - n        //           n is prime: return 1 - n, which results in f(2n - 1)
)(n)               //     initial call to g()
)                    //   end of recursive call to f()
:                      // else:
n % 38               //   return n % 38 (gives 19 as expected if n = 57)

• Smart, using 57%n and n%38 instead of n==3|n==19. Saved 1 byte in my Java answer as well, so thanks! – Kevin Cruijssen Oct 19 '17 at 11:22
• In ideone 57991 input generate prog.js:2:26 InternalError: too much recursion – RosLuP Oct 20 '17 at 10:24
• In tio f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38 print(f(57991)) generate stop program not output, it seems to me – RosLuP Oct 20 '17 at 10:30
• @RosLuP This is a code-golf challenge without any specific constraint. The current consensus is that speed or memory limitations (such as the call stack size) can be disregarded unless explicitly stated otherwise in the question. I take it for granted that the 1000000 limit is just informative because the sequence was not tested beyond that. Incidentally, your 70-byte solution is perfectly fine and is probably more relevant than the 93-byte version for a code-golf challenge. – Arnauld Oct 20 '17 at 10:57

# Jelly, 23 19 bytes

-4 bytes from miles. Still longer than 05AB1E, though.

Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿  Try it online! • Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿ using a while loop instead and some re-ordering – miles Oct 19 '17 at 11:44

# Python 2, 110105103 101 bytes

-2 bytes thanks to @Lynn

f=lambda n,i=2,k=0:i/n and(n*(n&~16==3)or f((2*i-1,k-i)[k>0]))or n%i and f(n,i+1,k)or f(n/i,2,k or n)


Try it online!

# Python 2, 116112 105 bytes

f=lambda n,i=2:i/n*i or n%i and f(n,i+1)or f(n/i)
n=input()
while~16&n-3:n=[2*n-1,n-f(n)][f(n)<n]
print n


Try it online!

• …n*(n&~16==3)or… saves 2 bytes. – Lynn Oct 19 '17 at 11:20
• For input 57991 sys.setrecursionlimit(20000) – RosLuP Oct 20 '17 at 6:34

# MATL, 22 21 bytes

Thanks to @Giuseppe for removing 1 byte!

tZp?Eq}tYfX>-]tI19h-


### Explanation

           % Do...while
t         %   Duplicate. Takes (implicit) input the first time
Zp        %   Is it prime?
?         %   If so
Eq      %     Times 2, minus 1
}         %   Else
t       %     Duplicate
YfX>-   %     Prime divisors, maximum, subtract
]         %   End
t         %   Duplicate
I19h      %   Push array [3 19]
-         %   Subtract, element-wise. The result is truthy if and only if
%   it doesn't contain any zero
% End (implicit). Next iteraton if top of the stack is truthy
% Display (implicit)


f 3=3
f 19=19
f n
|(c==[1])=f$2*n-1 |True=f$n-head c
where c=z n;v b=reverse[x|x<-[1..(b-1)],bremx==0];z j=case v j of[1]->[1];s->filter((==[1]).v)$s  Probably missing some golf tricks here, this is my first attempt at haskell golf. • Hello and welcome to the site. You don't need the newlines and spaces for pattern guards. You can also use 1>0 for True most times but often it might be better to use an assignment, for example c<-z n. – Ad Hoc Garf Hunter Oct 20 '17 at 1:10 • [x|x<-[b-1,b-2..1],rem b x==0] is also short than reverse[x|x<-[1..(b-1)],bremx==0]. – Ad Hoc Garf Hunter Oct 20 '17 at 1:11 • And one last thing, if you would like to discuss haskell golfing you can join us in Of Monads and Men. – Ad Hoc Garf Hunter Oct 20 '17 at 1:12 # Neim, 17 16 bytes ͻY𝐏𝕚÷D𝐌Ξᚫ<#D𝐏𝐠𝕊  Explanation: ͻ Start infinite loop D Duplicate Y Push 57 𝐏 Prime factors: [3 19] 𝕚 If the second-to-top of stack is in the list ÷ Break the loop D Duplicate 𝐌Ξᚫ< If prime, double and decrement #D𝐏𝐠𝕊 Otherwise, subtract the largest prime factor  Try it online! # R + numbers, 102 99 bytes function(n){while(!n%in%c(3,19))n="if"(isPrime(n),2*n-1,n-max(primeFactors(n))) n} library(numbers)  Try it online! R isn't known for short built-ins, and even the packages follow suit! # Java 8, 140135134 94 bytes n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;t/=m=f);return n%38;}  -5 bytes converting recursive Java 7 method to Java 8 lambda with loop. -1 byte implicit thanks to @Arnauld's JavaScript answer by changing n!=3&n!=19 and return n; to 57%n>0 and return n%38;. I think it should be possible to somehow combine the two loops and check if n is a prime, and get it's largest prime factor at the same time, but I can't figure it out (yet). So this will be the initial version for now. -40 whopping bytes thanks to @Nevay, by doing what I couldn't do: combining the loops to check for primes and largest prime factor at once. Explanation: Try it here (executes even 999999 in under 1 second). n->{ // Method with integer as both parameter and return-type for(int f, // Flag-integer t, // Temp-integer m=1; // Max prime factor integer, starting at 0 57%n>0; // Loop (1) as long as n is not 3, not 19 and not 57: n=f>n? // After every iteration: if f is larger than n: 2*n-1 // Change n to 2*n-1 : // Else: n-m) // Change n to n-m for(t=n, // Reset t to n f=1; // Reset f to 1 f++<t;) // Inner loop (2) from 2 to t (inclusive) for(;t%f<1; // Inner loop (3) as long as t is divisible by f t/=m=f; // Set m to f, and set t to t/f ); // End of inner loop (3) // End of inner loop (2) (implicit / single-line body) // End of loop (1) (implicit / single-line body) return n%38; // Return n%38, which is now either 3 or 19 } // End of method  • 1 character short of being a C# polyglot :( – Ian H. Oct 20 '17 at 7:44 • @IanH. Hehe, yes, that's usually the case: n=> instead of n->. And sometimes lowercase/uppercase calls. ;) – Kevin Cruijssen Oct 20 '17 at 8:08 • 94 bytes: n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;} – Nevay Oct 20 '17 at 10:06 • @Nevay Thanks! I just knew it should be possible to combine the loops, but couldn't figure it out. A whopping 40 bytes saved thanks to you! – Kevin Cruijssen Oct 20 '17 at 12:20 # Bash, 73 bytes ((57%$1))&&$0$[(x=$1-factor$1|sed 's/.* //')?x:2*$1-1]||echo$[$1%38]  Try it online! Modified slightly to work on TIO. Recursively calls its own script file using $0, which does not work in TIO because it must be ran as ./filename.sh. Accepts input as command-line argument.

Uses the same modulus trick as @Arnauld's JS answer.

$for t in 5 23 10 74 94 417 991 9983;{ echo -n "$t -> "; ./prime-frog.sh $t; } 5 -> 3 23 -> 3 10 -> 3 74 -> 19 94 -> 3 417 -> 3 991 -> 19 9983 -> 19  # Python 3, 97 bytes f=lambda n:n*(n&-17==3)or f(n-max(k*all(n%k<k%j for j in range(2,k))for k in range(n+1))or 2*n-1)  Try it online! • For 57991 input 1 minute was not sufficient – RosLuP Oct 20 '17 at 6:27 # Pyth, 19 bytes .W!/P57H?P_ZtyZ-ZeP  Verify all the test cases! The Husk answer inspired me to save 2 bytes (,3 19 to P57). ## How this works .W!/P57H?P_ZtyZ-ZeP - Full program. .W - Functional while. While A(value) is truthy, value = B(value). Returns the last value. P57 - The prime factors of 57 ([3, 19]). / H - Count the occurences of the current value. ! - Logical NOT. 0 -> Truthy, anything else -> Falsy. ?P_Z - If the current value is prime, then: tyZ - Double the current value, decrement. -ZeP - Else, Subtract the maximal prime factor of the current value from itself. - Print implicitly.  # PowerShell, 150 126 bytes for($n="$args";57%$n){$a=$n;$d=for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}};if($n-in$d){$n+=$n-1}else{$n-=$d[-1]}}$n%38


Try it online! (warning: slow for bigger numbers)

Iterative method. PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on Prime Factors Buddies.

First is our for loop. The setup sets $n to be the input value, and the conditional keeps the loop going so long as 57%$n is non-zero (thanks to Arnauld for that trick). Inside the loop we first get a list of prime factors of $a (set to $n). This is the code borrowed from Prime Factors Buddies. If the input $a is already prime, this will return just $a (important later). That (potentially just $a) gets stored into $d.

Next is an if/else conditional. For the if part, we check whether $n is -in $d. If it is, that means that $n is prime, so we take $n=2*$n-1 or $n+=$n-1. Otherwise, it's composite, so we need to find the largest prime factor. That means we need to take the last one [-1] of $d and subtract that from $n with $n-=. This works because we're looping up from 2 and thus the last element of $d is already going to be the largest. Once we're done looping, we just place $n%38 (again, thanks Arnauld) on the pipeline and output is implicit.

# APL (Dyalog Unicode), 11390 59 bytes

⎕CY 'dfns'
g←{1pco ⍵:f(2×⍵)-1⋄f⍵-⊃⌽3pco ⍵}
f←{⍵∊3 19:⍵⋄g ⍵}


Try it online!

TIO works with values up to ~3200. Tested on my PC for the last test case. To test on TIO, just add f value to the bottom of the code. Doesn't apply anymore, thanks to @Adám for pointing out that my primality checking algorithm was really bad and supplying me with a replacement; also for the 23 byte save.

Edited to fix byte count.

### How it works

⎕CY 'dfns'                      # Imports every Defined Function, which is shorter than importing just the function I used (pco).

g←{1pco ⍵:f(2×⍵)-1⋄f⍵-⊃⌽3pco ⍵}
g←                              # define g as
1pco ⍵:                      # if the argument ⍵ is prime
f(2×⍵)-1              # Call f over 2×⍵-1
⋄f            # else, call f over
⊃           # the first element of the
3pco ⍵    # list of prime factors of ⍵
⌽          # reversed

f←{⍵∊3 19:⍵⋄g ⍵}
f←                              # Define f as
⍵     :                      # if the argument ⍵
∊                           # is in
3 19                       # the list [3, 19]
⍵                     # return the argument ⍵
⋄                    # else
g ⍵                 # call g over the argument ⍵


# Axiom, 93 bytes

h(n)==(repeat(n=3 or n=19 or n<2=>break;prime? n=>(n:=2*n-1);n:=n-last(factors(n)).factor);n)


test:

(4) -> [[i,h(i)] for i in [10,74,94,417,991,9983]]
(4)  [[10,3],[74,19],[94,3],[417,3],[991,19],[9983,19]]
Type: List List Integer


There would be 68 bytes function

q x==(n<4=>3;n=19=>n;prime? n=>q(2*n-1);q(n-last(factors n).factor))


but for n=57991 (if I remember well) it goes out the stack space reserved.

# Python 2, 93 bytes

Port from TFeld's answer without external libs.

n=input()
while~16&n-3:
f=n;i=2
while i<f:
if f%i:i+=1
else:f/=i
n-=[1-n,f][f<n]
print n
`

Try it online!