Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Inspired by this Numberphile entry

Background

The cube distance numbers of an integer n are defined here as the set of integers that are distance away for a given x. For a simple example, with n=100 and x=2, the cube distance numbers are {92,108}.

This can be extended into a larger set simply by varying x. With x ∈ {1,2,3,4} and the same n=100, we have the resultant set {36,73,92,99,101,108,127,164}.

Let's define CD(n,x) as the set of all integers n ± z³ with z ∈ {1,2,3,...,x}.

Now we can focus on some of the special properties of these cube distance numbers. Of the many special properties that numbers can have, the two properties we're interested in here are primality and prime divisors.

For the above example CD(100,4), note that 73, 101, 127 are all prime. If we remove those from the set, we're left with {36,92,99,108,164}. All prime divisors of these numbers are (in order) {2,2,3,3,2,2,23,3,3,11,2,2,3,3,3,2,2,41}, which means we have 5 distinct prime divisors {2,3,23,11,41}. We can therefore define that CD(100,4) has ravenity1 of 5.

The challenge here is to write a function or program, in the fewest bytes, that outputs the ravenity of a given input.

Input

  • Two positive integers, n and x, in any convenient format.

Output

  • A single integer describing the ravenity of the two input numbers, when calculated with CD(n,x).

Rules

  • Input/output can be via any suitable method.
  • Standard loophole restrictions apply.
  • For ease of calculation, you can assume that the input data will be such that CD(n,x) will never have negative numbers in the set.
  • The function or program should be able to handle input numbers so that n + x³ fits in your language's native integer data type. For example, for a 32-bit signed integer type, all input numbers with n + x³ < 2147483648 are possible.

Examples

n,x   - output
2,1   - 0   (since CD(2,1)={1,3}, distinct prime divisors={}, ravenity=0)
5,1   - 2
100,4 - 5
720,6 - 11

Footnotes

1 - So named because we're not interested in the cardinality of the set, but a different type of bird. Since we're dealing with "common" divisors, I chose to use the common raven.

share|improve this question
    
How does 100,4 yield 5? The cube distance numbers of that set are 36,164, and the prime factors of that set are 2,3,41 (since the factors of that set are {2, 3, 4, 6, 9, 12, 18, 36} and {2, 4, 41, 82, 164} , respectively). Therefore, the output should be 3, not 5. – R. Kap 14 hours ago
2  
@R.Kap 100,4 is the example the OP explains in the Background section. Your mistake seems to be that you should consider all 1..x, so [1,2,3,4] for this case. – FryAmTheEggman 14 hours ago
    
@FryAmTheEggman Oh. okay. I get it now. – R. Kap 14 hours ago
1  
Can n == x³? I think some of the current answers fail in that case. – Dennis 13 hours ago
1  
@Dennis, all of the answers which use integer types for the output would fail, because there are infinitely many prime divisors of 0. – Peter Taylor 13 hours ago

10 Answers 10

Pyth - 21 19 18 bytes

I wonder if there's a trick.

l{st#mP+Q^d3s_BMSE

Test Suite.

l                   Length
 {                  Uniquify
  s                 Combine divisor lists
   t#               Filter by if more than one element
     PM             Take prime factorization of each number
       +RQ          Add each num in list to input
          s_BM      Each num in list and its negative (with bifurcate)
              ^R3   Cube each num in list
                 SE Inclusive unary range - [1, 2, 3,... n] to input
share|improve this answer

Jelly, 16 bytes

ŒRḟ0*3+µÆfFœ-µQL

Takes x and n as command-line arguments, in that order. Try it online!

How it works

ŒRḟ0*3+µÆfFœ-µQL  Main link. Arguments, x, n

ŒR                Range; yield [-x, ..., x].
  ḟ0              Filter out 0.
    *3            Cube each remaining integer.
      +           Add n to all cubes.
       µ          Begin a new, monadic link. Argument: A (list of sums)
        Æf        Factorize each k in A.
          F       Flatten the resulting, nested list.
           œ-     Perform multiset difference with A.
                  If k in A is prime (or 0), Æf returns [k], adding on k too many
                  to the flat list. Multiset difference with A removes exactly one
                  k from the results, thus getting rid of primes (and 0).
                  If k is composite (or 1), it cannot appear in the primes in the
                  flat list, so subtracting it does nothing.
             µ    Begin a new, monadic link. Argument: D (list of prime divisors)
              Q   Unique; deduplicate D.
               L  Compute the length of the result.
share|improve this answer

05AB1E, 20 19 bytes

Code:

L3mD(«-Dp_Ïvyf`})Úg

Input in the form x, n. Uses CP-1252 encoding.

Try it online!

share|improve this answer

MATL, 21 bytes

:3^t_h+tZp~)"@Yf!]vun

Input is x, n separated by a newline.

Try it online!

Explanation

:       % take n implicitly. Generate [1,2,...,n]
3^      % raise to 3, element-wise
t_h     % duplicate, negate, concatenate horizontally: [1,2,...,n,-1,2,...-n]
+       % take x implicitly. Add to that array
t       % duplicate
Zp      % array that contains true for primes
~       % logical negate
)       % apply index to keep only non-primes
"       % for each number in that array
  @     %   push that number
  Yf!   %   prime factors, as a column array
]       % end for each
v       % concatenate vertically all factors
u       % remove repeated factors
n       % number of elements of that array. Implicitly display
share|improve this answer

J, 30 bytes

#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:

This is a dyadic verb, used as follows:

   f =: #@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
   100 f 4
5

Try it here.

Explanation

#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
                            i:  Range from -x to x
                    (     )@    Apply this verb to the range:
                       ^&3        a) every item cubed
                     |            b) absolute value of every item
                      #           c) every item in a) repeated b) times; this removes 0
                                     and produces some harmless duplication
                   +            Add n to every element of the resulting list
     (          )@:             Apply this verb to the resulting vector:
             0&,                  a) the vector with 0 appended
      ,@:q:                       b) flat list of prime divisors in the vector
                                     (and some extra 0s since we flatten an un-even matrix)
           -.                     c) list b) with elements of a) removed; this gets rid of
                                     the extra 0s and all primes that were in the list
#@~.@                           Remove duplicates and take length
share|improve this answer
2  
@:+( why so sad, awesome-hair-guy? – TimmyD 15 hours ago
    
Link to TIO in answer please? – Easterly Irk 14 hours ago
    
@EasterlyIrk TIO doesn't have J. I'll add a link to tryj.tk. – Zgarb 14 hours ago
    
@Zgarb okai.___ – Easterly Irk 14 hours ago

Julia, 112 bytes

f(n,x)=endof(∪(foldl(vcat,map(k->[keys(factor(k))...],filter(i->!isprime(i)&&i>0,[n+z^3for z=[-x:-1;1:x]])))))

This is a function that accepts two integers and returns an integer.

Ungolfed:

function f(n, x)
    # Get all cube distance numbers
    cubedist = [n + z^3 for z = [-x:-1; 1:x]]

    # Filter out the primes and zeros
    noprimes = filter(i -> !isprime(i) && i > 0, cubedist)

    # Factor each remaining number
    factors = map(k -> [keys(factor(k))...], noprimes)

    # Flatten the list of factors
    flat = foldl(vcat, factors)

    # Return the number of unique elements
    return endof(∪(flat))
end
share|improve this answer

Ruby, 132 120 114 bytes

I'm well aware that this solution still needs a lot of golfing. Any golfing tips are welcome.

require'prime'
->n,x{(-x..x).map{|i|j=n+i**3;j.prime?||(j==n)?[]:j.prime_division.map{|z|z[0]}}.flatten.uniq.size}

Ungolfing:

require 'prime'

def ravenity(n, x)
  z = []
  (-x..x).each do |i|
    j = n + i**3
    m = j.prime_division
    if j.prime? || j == n
      z << []
    else
      z << m.map{|q| q[0]}
    end
  return z.flatten.uniq.size
end
share|improve this answer

PARI/GP, 79 bytes

(n,x)->omega(factorback(select(k->!isprime(k),vector(2*x,i,n+(i-(i<=x)-x)^3))))

Here is my original straightforward implementation. The optimized version above combines the two vectors into a single, slightly more complicated vector.

(n,x)->omega(factorback(select(k->!isprime(k),concat(vector(x,i,n-i^3),vector(x,i,n+i^3)))))
share|improve this answer
    
This is really interesting. I see there's an in-browser link to try the code, but I'm not sure how to actually submit the input. Can you provide an explanation? – TimmyD 14 hours ago
    
@TimmyD: If you assign either of the above to f (like f=(n,x)->...) then you can test it with f(100,4). Alternately, you can invoke it in one line with ((n,x)->...)(100,4). – Charles 14 hours ago
    
@TimmyD: Although note that the online version doesn't work for Chrome at the moment, so use Firefox or something. – Charles 14 hours ago

Python 3.5, 218 bytes:

lambda r,n:len({z for z in{v for f in{t for u in[[r-q**3,r+q**3]for q in range(1,n+1)]for t in u if any(t%g==0 for g in range(2,t))}for v in range(2,f)if f%v==0}if all(z%g!=0 for g in range(2,z))and z%1==0 and z%z==0})

A nice one-lined lambda function, although it may be a bit long. Since I was using Python, I had to come up with my own way of finding the composites for the first step, and then the prime divisors for the last step, so it was not very easy, and this was the shortest I, by myself. could get it to. Nonetheless, it does what it needs to, and I am proud of it. :) However, any tips for golfing this down a bit more are welcome.

share|improve this answer

Ruby, 138 bytes

->(n,x){require'prime'
v=((-x..x).to_a-[0]).map{|i|n+i**3}.reject{|e|Prime.prime?(e)}
Prime.each(v[-1]).select{|i|v.any?{|e|e%i==0}}.size}

It was a puny challenge. :-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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