Ravenity of Cube Distance Numbers

Question

_{Inspired by this Numberphile entry}

Background

The cube distance numbers of an integer n are defined here as the set of integers that are x³ 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 ravenity¹ 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 only have positive numbers in the set (i.e., no CD(n,x) will ever have negative numbers or zero).
• 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.

Answer 1

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, Æ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.
                  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.

Answer 2

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

Answer 3

Julia, 107 bytes

f(n,x)=endof(∪(foldl(vcat,map(k->[keys(factor(k))...],filter(i->!isprime(i),[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

Answer 4

05AB1E, 20 19 bytes

Code:

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

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

Try it online!

Answer 5

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

Answer 6

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

Answer 7

Python 3.5, 218 198 bytes:

(Thanks to @Blue for saving me 20 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<1 for g in range(2,t))}for v in range(2,f)if f%v<1}if all(z%g>0 for g in range(2,z))})

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.

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

Python 3.5 - 177 175 159 bytes

Any golfing tips welcome :)

a=range
p=lambda n:any(n%x<1for x in a(2,n))
r=lambda n,x:len(set(sum([[x for x in a(2,z+1)if z%x<1&1>p(x)]for z in filter(p,[n+z**3for z in a(-x,x+1)])],[])))

Ungolfed:

def is_composite(n):
    return any(n % x == 0 for x in range(2, n))

def prime_factors(n):
    return {x for x in range(2, n+1) if n % x == 0 and not is_composite(x)}

def ravenity(n, x):
    nums = [n + z**3 for z in range(-x, x+1)]
    nums = filter(is_composite, nums)
    factors = map(prime_factors, nums)
    factors = sum(factors, [])
    #remove duplicates
    factors = set(factors)
    return len(factors)

Answer 12

Wolfram Language (Mathematica), 90 bytes

Tr[1^Union[First/@Join@@FactorInteger/@Select[z=Range@#2^3;Join@@{#-z,#+z},Not@*PrimeQ]]]&

Try it online!

un-golfed: the code is read mostly from right to left,

F[n_, x_] := 
  Length[Union[                                        (* number of unique elements   *)
    First /@                                           (* drop multiplicities         *)
      Join @@                                          (* join all prime factor lists *)
        FactorInteger /@                               (* compute prime factors       *)
          Select[                                      (* select those...             *)
            Join @@ {n - Range[x]^3, n + Range[x]^3},  (* ...candidates...            *)
            Not@*PrimeQ]]]                             (* ...that are not prime       *)