Find a Rocco number

Question

I was asked this question in an interview but I was unable to figure out any solution. I don't know whether the question was right or not. I tried a lot but couldn't reach any solution. Honestly speaking, nothing came to my mind.

Rocco numbers

A positive integer \$n\$ is a Rocco number if it can be represented either as \$n=p(p+14)\$ or \$n=p(p-14)\$, where \$p\$ is a prime number.

The first 10 Rocco numbers are:

$$32, 51, 95, 147, 207, 275, 351, 435, 527, 627$$

Task

Your code must accept a positive integer as input and determine if it is a Rocco number or not.

Brownie points

• Write a function that calculates and prints the count of Rocco numbers less than or equal to 1 million.
• Write a function that calculates and prints the count of Rocco numbers from the bonus question (above one) that are prime.

Answer 1

05AB1E, 8 bytes

Returns \$1\$ if \$n\$ is a Rocco number, or \$0\$ otherwise.

fDŠ/α14å

Try it online!

How?

Given a positive integer \$n\$, we test whether there exists a prime factor \$p\$ of \$n\$ such that:

$$\left|p-\frac{n}{p}\right|=14$$

Commented

fDŠ/α14å  # expects a positive integer n as input       e.g. 2655
f         # push the list of unique prime factors of n  -->  2655, [ 3, 5, 59 ]
 D        # duplicate it                                -->  2655, [ 3, 5, 59 ], [ 3, 5, 59 ]
  Š       # moves the input n between the two lists     -->  [ 3, 5, 59 ], 2655, [ 3, 5, 59 ]
   /      # divide n by each prime factor               -->  [ 3, 5, 59 ], [ 885, 531, 45 ]
    α     # compute the absolute differences
          # between both remaining lists                -->  [ 882, 526, 14 ]
     14å  # does 14 appear in there?                    -->  1

Answer 2

JavaScript (ES7), 55 bytes

n=>(g=k=>k>0&&n%--k?g(k):k==1)(n=(49+n)**.5-7)|g(n+=14)

Try it online!

How?

Given a positive integer \$n\$, we're looking for a prime \$x\$ such that \$x(x+14)=n\$ or \$x(x-14)=n\$.

Hence the following quadratic equations:

$$x^2+14x-n=0\tag{1}$$ $$x^2-14x-n=0\tag{2}$$

The positive root of \$(1)\$ is:

$$x_0=\sqrt{49+n}-7$$

and the positive root of \$(2)\$ is:

$$x_1=\sqrt{49+n}+7$$

Therefore, the problem is equivalent to testing whether either \$x_0\$ or \$x_1\$ is prime.

To do that, we use the classic recursive primality test function, with an additional test to make sure that it does not loop forever if it's given an irrational number as input.

g = k =>    // k = explicit input; this is the divisor
            // we assume that the implicit input n is equal to k on the initial call
  k > 0 &&  // abort if k is negative, which may happen if n is irrational
  n % --k ? // decrement k; if k is not a divisor of n:
    g(k)    //   do a recursive call
  :         // else:
    k == 1  //   returns true if k is equal to 1 (n is prime)
            //   or false otherwise (n is either irrational or a composite integer)

Main wrapper function:

n => g(n = (49 + n) ** .5 - 7) | g(n += 14)

Answer 3

Perl 6, 45 28 bytes

((*+49)**.5+(7|-7)).is-prime

Try it online!

Uses Arnauld's construction, that \$\sqrt{n+49}\pm7\$ must be prime for \$n\$ to be a Rocco number.

Explanation:

 (*+49)**.5                   # Is the sqrt of input+49
           +(7|-7)            # Plus or minus 7
(                 ).is-prime  # Prime?

Answer 4

Regex (ECMAScript), 64 62 bytes

This regex finds two numbers \$a\$ and \$a+14\$ such that \$n=a(a+14)\$. If it finds them, it then asserts that either \$a\$ or \$a+14\$ is prime. That's it!

This uses a variant of the multiplication algorithm briefly described in a paragraph of my abundant numbers regex post. This is a spoiler. So do not read any further if you don't want some advanced unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in the list of consecutively spoiler-tagged recommended problems in this earlier post, and trying to come up with the mathematical insights independently.

The multiplication algorithm is implemented differently here because we are asserting that two known values multiplied together equal another known value (as also done in the alternative version of the regex in this post, to test for a number being a perfect square). In most of my other posted regex answers so far, multiplication is implemented as a calculation (not an assertion, conceptually speaking) where the goal is to find the product of two known numbers. Both methods work in both circumstances, but golf-wise, are worse at doing each other's job.

^(?=(x((x{14})(x+)))(?=(\1*)\4\2*$)(\1*$\5))\6\3?(?!(xx+)\7+$)

Try it online!

 # For the purposes of these comments, the input number = N.
 ^
 # Find two numbers A and A+14 such that A*(A+14)==N.
 (?=
     (x((x{14})(x+)))   # \1 = A+14; \2 = \1-1; \3 = 14; \4 = A-1; tail -= \1
     (?=                # Assert that \1 * (\4+1) == N.
         (\1*)\4\2*$    # We are asserting that N is the smallest number satisfying
                        # two moduli, thus proving it is the product of A and A+14
                        # via the Chinese Remainder Theorem. The (\1*) has the effect
                        # of testing every value that satisfies the "≡0 mod \1"
                        # modulus, starting with the smallest (zero), against "\4\2*$",
                        # to see if it also satisfies the "≡\4 mod \2" modulus; if any
                        # smaller number satisfied both moduli, (\1*) would capture a
                        # nonzero value in \5. Note that this actually finds the
                        # product of \4*\1, not (\4+1)*\1 which what we actually want,
                        # but this is fine, because we already subtracted \1 and thus
                        # \4*\1 is the value of tail at the start of this lookahead.
                        # This implementation of multiplication is very efficient
                        # golf-wise, but slow, because if the number being tested is
                        # not even divisible by \1, the entire test done inside this
                        # lookahead is invalid, and the "\1*$" test below will only
                        # fail after this useless test has finished.
     )
     (\1*$\5)           # Assert that the above test proved \1*(\4+1)==N, by
                        # asserting that tail is divisible by \1 and that \5==0;
                        # \6 = tool to make tail = \1
 )
 # Assert that either A or A+14 is prime.
 \6                     # tail = \1 == A+14
 \3?                    # optionally make tail = A
 (?!(xx+)\7+$)          # Assert tail is prime. We don't need to exclude treating
                        # 1 as prime, because the potential false positive of N==15
                        # is already excluded by requiring \4 >= 1.
 

Answer 5

Brachylog, 13 12 bytes

ṗ;14{+|-};?×

Enter the candidate number as a command-line argument. Outputs true or false. Try it online!

Explanation

The code is a predicate whose input is unconstrained and whose output is the number we're testing.

ṗ             Let the input ? be a prime number
 ;14          Pair it with 14, yielding the list [?, 14]
    {+|-}     Either add or subtract, yielding ?+14 or ?-14
         ;?   Pair the result with the input, yielding [?+14, ?] or [?-14, ?]
           ×  Multiply; the result must match the candidate number

(Tips are welcome. That {+|-} still feels clunky.)

Answer 6

Brachylog, 9 bytes

Different approach then DLosc's answer

Ċ-14&∋ṗ&×

Takes N as output, gives [P, P-14] or [P+14,P] back through input (biggest number first)

explanation

Ċ              # The 'input' is a pair of numbers
 -14           #   where the 2nd is 14 smaller then the first
    &∋ṗ        #   and the pair contains a prime
       &×      #   and the numbers multiplied give the output (N)

Try it online!

Answer 7

Pyth, 22 20 bytes

}Qsm*Ld+Ld_B14fP_TSh

Try it online here.

}Qsm*Ld+Ld_B14fP_TShQ   Implicit: Q=eval(input())
                        Trailing Q inferred
                  ShQ   Range [1-(Q+1)]
              fP_T      Filter the above to keep primes
   m                    Map the elements of the above, as d, using:
          _B14            [14, -14]
       +Ld                Add d to each
    *Ld                   Multiply each by d
  s                     Flatten result of map
}Q                      Is Q in the above? Implicit print

Edit: Saved 3 bytes as input will always be positive, so no need to filter out negative values from the list. Also fixed a bug for inputs 1 and 2, costing 1 byte. Previous version: }Qsm*Ld>#0+Ld_B14fP_TU

Answer 8

05AB1E, 16 15 14 bytes

Saved 1 byte by computing 14 with 7· instead of žvÍ (cant believe I didnt think of this in the first place).

Saved 1 byte thanks to Emigna

ÅPε7·D(‚+y*Q}Z

Try it online! or Test all inputs

Explanation

                 # Implicit input n
ÅP               # Push a list of primes up to n
  ε         }    # For each prime in the list...
   7·            # Push 14 (by doubling 7)
     D(‚         # Push -14 and pair them together to get [14,-14]
        +        # Add [14,-14] to the prime
         y*      # Multiply the prime to compute p(p-14) and p(p+14)
           Q     # Check if the (implicit) input is equal to each element
             Z   # Take the maximum

Answer 9

J, 21 15 bytes

Based on Arnauld's solution:

14 e.q:|@-(%q:)

Try it online!

Previous atempt:

e.&,14&(]*+,-~)@p:@i.

Try it online!

Answer 10

Retina 0.8.2, 61 bytes

.+
$*
^((1{14})1(1)+)(?<=(?<!^\4+(..+))\2?)(?<-3>\1)+$(?(3)1)

Try it online! Explanation:

.+
$*

Convert to unary.

^((1{14})1(1)+)

\1 captures the larger of the two factors. \2 captures the constant 14, saving a byte. \3 captures the smaller of the two factors, minus 1. This also ensures that both factors are at least 2.

(?<=(?<!^\4+(..+))\2?)

Check the two factors to ensure at least one of them is prime. The idea of using \2? was shamelessly stolen from @Deadcode's answer.

(?<-3>\1)+

Repeat the larger of the two factors a number of times equal to one less than the smaller of the two factors. As we've already captured the larger factor once this then ends up capturing the product of the two factors.

$(?(3)1)

Ensure that the product equals the given number.

A direct translation to Retina 1 by replacing $* with *1 would have the same byte count but a byte could be saved by replacing all the 1s with _s and then the *1 could be replaced with * rather than *_. Previous Retina 1 answer for 68 bytes:

.+
*
Lw$`^(__+)(?=(\1)+$)
$1 _$#2*
Am` (__+)\1+$
(_+) \1

0m`^_{14}$

Try it online! Explanation:

.+
*

Convert to unary.

Lw$`^(__+)(?=(\1)+$)
$1 _$#2*

Find all the pairs of factors.

Am` (__+)\1+$

Ensure one is prime.

(_+) \1

Take the absolute difference.

0m`^_{14}$

Check whether any are 14.

Answer 11

JavaScript (Babel Node), 69 bytes

Damn, I though I was going to beat Arnaulds' Answer but no..... :c

x=>[...Array(x)].some((a,b)=>x/(a=(p=n=>--b-1?n%b&&p(n):n)(b))-a==14)

Try it online!

I want to get rid of the x=>[...Array(x)].some( part using recursion so it might get shorter over time

Explanation

x=>[...Array(x)]                                                              Creates a range from 0 to x-1 and map:

                .some((a,b)=>                                                 Returns True if any of the following values is true
                             x/                                              Input number divided by
                                (a=(p=n=>--b-1?n%b&&p(n):n)(b))               recursive helper function. Receives a number (mapped value) as parameters and returns 
                                                                              the same number if it is prime, otherwise returns 1. Take this value
                                                                              and assign to variable a
                                                               -a            Subtract a from the result  
                                                                     ==14    Compare result equal to 14

It uses the formula

$$ n/p-p==14 $$

Answer 12

Japt, 10 bytes

Same as my Javascript Answer

k d@/X-X¥E

Try it online!

Answer 13

Jelly, 9 bytes

:ạ⁹ɗÆf14e

Try it online!

Answer 14

APL(NARS) 16 chars, 32 bytes

{14=∣r-⍵÷r←↑⌽π⍵}

{π⍵} would find the factorization of its argument and we suppose that the last element of its result (the list of divisors of n) is the maximum prime divisor of n; Here we suppose that one equivalent definition of Rocco number is: n is a Rocco number <=> max factor prime of n: r is such that it is true 14=∣r-n÷r [for C pseudocode as 14==abs(r-n/r) this definition of Rocco number seems ok at last in the range 1..1000000]; the range of ok value would be 1..maxInt; test:

 f←{14=∣r-⍵÷r←↑⌽π⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨1..10000
32  51  95  147  207  275  351  435  527  627  851  1107  1247  1395  1551  1887  2067  2255  2451  2655  2867  3551  4047  4307  4575  5135  5427  5727  6035  6351  6675  7347  8051  8787  9167  9951   

Answer 15

C# (Visual C# Interactive Compiler), 99 bytes

n=>Enumerable.Range(2,n).Any(p=>Enumerable.Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Try it online!

Enumerable.Range strikes again :) Using the crazy compiler flag, you can reduce things quite a bit, although I am kind of a fan of the vanilla solution.

C# (Visual C# Interactive Compiler) + /u:System.Linq.Enumerable, 77 bytes

n=>Range(2,n).Any(p=>Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Try it online!

Below is a port of Arnauld's solution that seemed pretty cool. It is currently the longest, but it can probably be golfed some.

C# (Visual C# Interactive Compiler), 101 bytes

n=>{bool g(int k)=>--k<2?n>1:n%k>0&g(k);var d=Math.Sqrt(n+49)-7;return(n=(int)d)==d&(g(n)|g(n+=14));}

Try it online!

Answer 16

Husk, 10 bytes

€14mS≠`/¹p

Try it online! Given an integer, the function outputs a truthy or falsy value. A port of Arnauld's answer.

Answer 17

APL(NARS) 30 chars, 60 bytes

{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}

Here 0π is the function say if one number is a prime, test:

 f←{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨0..700
32  51  95  147  207  275  351  435  527  627

Answer 18

F#, 2 answers (noncompeting)

I really liked @Arnauld 's answers, so I translated them.

123 bytes, based on the JavaScript answer

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||)

Explanation:

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||) //Lambda which takes an integer, n
       let t=int<|sqrt(float n+49.)                                                                                         //let t be n, converted to float, add 49 and get square root, converted back to int (F# type restrictions)
                                   in                                                                                       //in the following...
                                                                                                  [t-7;t+7]                 //Subtract and add 7 to t in a list of 2 results (Lists and Seqs can be interchanged various places)
                                      Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)                          //See if either are prime (here, if either result has 2 and only 2 divisors)
                                                                                                           |>Seq.reduce(||) //And logically OR the resulting sequence

125 bytes, based on the 05AB1E answer

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14

Explanation:

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14  //Lambda which takes an integer, n
       let l=Seq.filter(fun i->n%i=0)[2..n-1]                                                                                  //let l be the list of n's primes 
                                             in                                                                                //in...
                                                let m=Seq.map(fun i->n/i)l                                                     //m, which is n divided by each of l's contents
                                                                           in                                                  //and then...
                                                                              Seq.map2(fun a b->abs(a-b))l m                   //take the absolute difference between each pair of items in the two sequences to make a new sequence
                                                                                                            |>Seq.contains 14  //and does the resulting sequence contain the number 14?

Answer 19

Python 2, 58 bytes

Outputs by exit code, fails (1) for Rocco numbers.

P=k=1.
n=input()
exec"P*=k*k;k+=1;P%k*abs(n/k-k)==14>y;"*n

Try it online!