12
\$\begingroup\$

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.
\$\endgroup\$
14
  • 5
    \$\begingroup\$ Hi and welcome to PPCG. We host challenges (your's looks really interesting) that have objective scoring and winning criteria. Try editing your post to include that. I recommend code-golf as the goal, since it is the easiest to get right. Also, you want to avoid those bonuses; just focus on one clear task. \$\endgroup\$ – Adám Jan 29 '19 at 20:19
  • 3
    \$\begingroup\$ output would be an integer: Don't you mean a Boolean for whether the input was a Rocco number or not? \$\endgroup\$ – Adám Jan 29 '19 at 20:20
  • 5
    \$\begingroup\$ Bonus 2: print 0. All Rocco numbers are composite (n*..), so no primes in any range. \$\endgroup\$ – TFeld Jan 29 '19 at 20:29
  • 5
    \$\begingroup\$ The "bonus points" can simply be hardcoded values, and aren't beneficial to the challenge at all. I recommend removing them. \$\endgroup\$ – Erik the Outgolfer Jan 30 '19 at 10:56
  • 5
    \$\begingroup\$ I've edited the question and the tags. Feel free to either rollback or edit further if you do not agree. As @EriktheOutgolfer said, I think the bonuses should be removed. \$\endgroup\$ – Arnauld Jan 30 '19 at 11:09

19 Answers 19

11
\$\begingroup\$

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
\$\endgroup\$
11
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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?
\$\endgroup\$
6
\$\begingroup\$

Regex (ECMAScript), 64 62 bytes

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

Try it online!

Takes its input in unary, as a sequence of x characters whose length represents the number.

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.

The multiplication algorithm implemented here searches for two unknown factors which, when multiplied together, equal a known product. The regex for this is also essentially equivalent to that of the shortest form of multiplication for asserting that two known factors multiply to make a known product.

In many of my other posted regex answers, multiplication is implemented as finding the unknown product of two known factors; the shortest form of that is different. Both methods would work in both circumstances, but golf-wise, they're worse at doing each other's job.

Here is an explanation of how this form of multiplication works in general:

We have \$AB \stackrel{?}{=} C\$, where \$A \ge B\$. The steps to asserting \$AB=C\$ are (shown here in an order that's easier to explain conceptually; in the regex they're done in the order that results in the best golf):

  • Assert that \$C-A \equiv 0 \pmod A\$
    • This is equivalent to \$C \equiv 0 \pmod A\$, a direct consequence of \$C=AB\$
  • Assert that \$C-A-(B-1) \equiv 0 \pmod {A-1}\$,
    • This can be shown to result from \$C=AB\$:
      \$\begin{aligned}C-A-(B-1) &= AB-A-(B-1) \\ &= A(B-1)-(B-1) \\ &= (A-1)(B-1)\end{aligned}\$
  • Assert that there is no \$0<D<C\$ which satisfies both of the above with \$D\$ in place of \$C\$

This can be expressed as:

  • Assert that the only \$0<E \le C-A\$ that satisfies the following moduli is \$E=C-A\$:
    • \$E \equiv 0 \pmod A\$
    • \$E \equiv B-1 \pmod {A-1}\$

We now have two coprime moduli, \$A\$ and \$A-1\$. By the Chinese remainder theorem, there is one and only one integer \$E\$ such that \$0 < E \le A(A-1)\$, or alternatively stated, \$0 < E+A \le A^2\$, and the above moduli are satisfied. And since we know \$B\le A\$, it follows that \$AB\le A^2\$.

The algebra above shows there is at least one \$E\$ satisfying the moduli: \$E=AB-A\$. The Chinese remainder theorem shows that there is exactly one \$E\$ satisfying the moduli within a certain range. The fact that \$B\le A\$ guarantees that \$AB-A\$ falls inside that range. We are not guaranteed that \$C\le A^2\$, but as long as we search for the smallest \$E\$ satisfying the moduli, we're guaranteed that \$E=AB-A\$, so if \$E=C-A\$, then \$AB=C\$.

The regex essentially searches for the smallest \$E\$ satisfying the moduli, then asserts that \$E=C-A\$. The assertion of \$C \equiv 0 \pmod A\$ is done afterward, making the regex a bit slower in the name of golf.

Also note that in regex, \$0 \equiv 0 \pmod 0\$, so the algorithm works for \$A=1\$ without any need for a special case.

In cases where we don't know whether \$A\ge B\$, and can't capture them at the source in such a way as to automatically sort them as such, we can simply assert both versions of each:

  • \$C \equiv 0 \pmod A\$
  • \$C \equiv 0 \pmod B\$
  • \$C-B \equiv 0 \pmod {A-1}\$
  • \$C-A \equiv 0 \pmod {B-1}\$

This makes for shorter golf than actually sorting \$A\$ and \$B\$ into lesser and greater after they've already been captured. But for this particular problem, only the two assertions need to be used, since by definition \$A=B+14\$.

And the regex, pretty-printed and commented:

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

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 16 15 14 bytes

Saved 1 byte by computing 14 with 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a byte by changing }˜så to Q}Z utilizing implicit input. Your Test-Suite would have to be changed up a bit to something like this to get it to work then. Also, a more obvious way of writing žvÍ or would be 14 ;) \$\endgroup\$ – Emigna Feb 1 '19 at 11:55
  • \$\begingroup\$ Thanks! Why make it easy when you can push 14 in the most complicated way /facepalm :) \$\endgroup\$ – Wisław Feb 1 '19 at 13:02
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 14 e.q:|@-]%q: for 14 bytes \$\endgroup\$ – Jonah Feb 16 '19 at 18:11
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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 $$

\$\endgroup\$
1
\$\begingroup\$

Japt, 10 bytes

Same as my Javascript Answer

k d@/X-X¥E

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 bytes

:ạ⁹ɗÆf14e

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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   
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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?
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.