15
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – R. Kap Apr 1 '16 at 20:31
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – FryAmTheEggman Apr 1 '16 at 20:33
  • \$\begingroup\$ @FryAmTheEggman Oh. okay. I get it now. \$\endgroup\$ – R. Kap Apr 1 '16 at 20:34
  • \$\begingroup\$ Would it be pronounced [ruh-VEE-nuh-tee] (or /rəˈviːnəti/ for those of you who read IPA)? \$\endgroup\$ – Leaky Nun Apr 2 '16 at 5:23
  • 1
    \$\begingroup\$ @KennyLau In my head, I pronounced it as "rah-VIN-eh-ty" \$\endgroup\$ – AdmBorkBork Apr 4 '16 at 14:41

12 Answers 12

4
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ The spec has been updated; you don't have to worry about 0's anymore. \$\endgroup\$ – Dennis Apr 8 '16 at 17:54
  • \$\begingroup\$ @Dennis Nice, thanks for the heads up. \$\endgroup\$ – Alex A. Apr 8 '16 at 19:10
2
\$\begingroup\$

05AB1E, 20 19 bytes

Code:

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

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

Try it online!

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

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

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
\$\endgroup\$
  • 2
    \$\begingroup\$ @:+( why so sad, awesome-hair-guy? \$\endgroup\$ – AdmBorkBork Apr 1 '16 at 19:18
  • \$\begingroup\$ Link to TIO in answer please? \$\endgroup\$ – Rɪᴋᴇʀ Apr 1 '16 at 20:23
  • \$\begingroup\$ @EasterlyIrk TIO doesn't have J. I'll add a link to tryj.tk. \$\endgroup\$ – Zgarb Apr 1 '16 at 20:24
  • \$\begingroup\$ @Zgarb okai.___ \$\endgroup\$ – Rɪᴋᴇʀ Apr 1 '16 at 20:25
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Couple things: don't use ==0, use <1, and for !=0, >0. Also, why the z%1 and z%z at the end? Those seem like they will always be true. \$\endgroup\$ – Blue Apr 2 '16 at 12:07
  • \$\begingroup\$ @Blue Yeah, you're right. They will always be true, so that part is not even needed. So, I'll remove that. And also, thanks for those other tips! :) \$\endgroup\$ – R. Kap Apr 2 '16 at 19:57
1
\$\begingroup\$

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)))))
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – AdmBorkBork Apr 1 '16 at 20:45
  • \$\begingroup\$ @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). \$\endgroup\$ – Charles Apr 1 '16 at 21:00
1
\$\begingroup\$

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

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

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

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

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       *)
\$\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.