The prime frog 🐸

Question

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).

Answer 1

Python 2, 101 93 92 90 88 87 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!

Answer 2

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!

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

Wolfram Language (Mathematica), 65 66 68 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:

Answer 7

05AB1E, 19 18 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

Answer 8

JavaScript (ES6), 73 71 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)

Answer 9

Jelly, 23 19 bytes

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

Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿

Try it online!

Answer 10

Python 2, 110 105 103 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, 116 112 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!

Answer 11

MATL, 22 21 bytes

Thanks to @Giuseppe for removing 1 byte!

`tZp?Eq}tYfX>-]tI19h-

Try it online! Or verify all test cases.

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)

Answer 12

Haskell - 154 bytes

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)],b`rem`x==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.

Answer 13

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!

Answer 14

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!

Answer 15

Java 8, 140 135 134 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

Answer 16

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.

Test Cases

$ 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

Answer 17

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!

Answer 18

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.

Answer 19

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.

Answer 20

APL (Dyalog Unicode), 113 90 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 ⍵

Answer 21

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.

Answer 22

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!