Closest 7-Distinct-Prime Product

Question

_{(via chat)}

The OEIS entry A123321 lists the sequence of numbers that are the product of seven distinct primes. For brevity, we'll call this a 7DP number. The first few numbers and their corresponding divisors are below:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

The challenge here will be to find the closest 7DP number, in terms of absolute distance, from a given input.

Input

A single positive integer n in any convenient format.

Output

The closest 7DP number to n, again in any convenient format. If two 7DP numbers are tied for closest, you can output either or both.

Rules

• Numbers can be assumed to fit in your language's default [int] datatype (or equivalent).
• Either a full program or a function are acceptable.
• Standard loopholes are forbidden.
• This is code-golf, so all usual golfing rules apply, and the shortest code wins.

Examples

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Answer 1

Python, 89 86 85 bytes

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

The algorithm is O(scary) to begin with and the recursion doesn't really help, but it works well as long as n is sufficiently close to a 7DP number.

Thanks to @xnor for golfing off 3 bytes!

Test it on repl.it.

How it works

Python has no primality or factorization built-ins, but we can identify 7DP numbers by the amount and nature of their divisors.

By the multiplication principle, the number of divisors of an integer can be computed as the product of the incremented exponents of its prime factorization. Thus, σ₀(n) (divisor function) is 2^m whenever n is a mDP number.

σ₀(n) = 128 is thus a necessary condition, but it is not sufficient; for example, σ₀(2¹²⁷) = 128, but 2¹²⁷ is clearly not a 7DP number. However, if both σ₀(n) = 128 and no perfect square divides n evenly, then n is a 7DP number.

For the input n, the algorithm consists in inspecting the integers n, n - 1, n + 1, n - 2, n + 2, etc. and returning the first one that is a 7DP number.

When f is called with argument n, the following happens:

• The code

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))
  

  tests if n is not a 7DP number as follows.

  For all integers i such that 1 < i < n, 1>>n%i<<7*(n/i%i<1) gets evaluated.

  • If n is divisible by i but not by i², 1>>n%i yields 1 and (n/i%i<1) yields 0, resulting in
    1 · 2^{7 · 0} = 1.

  • If n is divisible by i², 1>>n%i and (n/i%i<1) both yield 1, resulting in 1 · 2^{7 · 1} = 128.

  • If n not not divisible by i, 1>>n%i yields 0, resulting in 0 · 2^{7 · x} = 0.

  ​
  The sum of the resulting integers will be 2^m - 2 if n is a mDP number (its 2^m divisors, excluding 1 and n) and a number greater than 127 if n has a perfect square factor. Thus, the sum will be 126 if and only if n is a 7DP number.

• For 7DP numbers, the sum is 126, so XORing it with 126 yields 0, which is falsy. Thus, the or part of the lambda is executed and f returns the current value of n.

• If n is not a 7DP number, XOR will return a non-zero, truthy value. Thus, the and part of the lambda is executed.

  f(n+k,k%2*2+~k)
  

  recursively calls f with updated values of n (the next potential 7DP number) and k (the difference between the the new candidate and the one after that).

  If k is an even, non-negative integer, k%2*2 yields 0 and ~k yields -(k + 1). The sum of both results is -(k + 1), which is an odd, negative integer that is 1 greater in absolute value than k.

  If k is an odd, negative integer, k%2*2 yields 2 and ~k yields -(k + 1). The sum of both results is 2 - (k + 1) = -(k - 1), which is an even, non-negative integer that is 1 unit greater in absolute value than k.

  This means that k takes the values 0, -1, 2, -3, 4, ⋯.

  When added cumulatively to n₀ (the initial value of n), the resulting integers are

  • n₀ + 0
  • (n₀ + 0) - 1 = n₀ - 1
  • (n₀ - 1) + 2 = n₀ + 1
  • (n₀ + 1) - 3 = n₀ - 2
  • (n₀ - 2) + 4 = n₀ + 2
  • etc.

  ​
  making sure the first 7DP number we encounter is as close to n₀ as possible.

Answer 2

Brachylog, 44 40 16 bytes

_{Crossed out 44 is still regular 44 ;(}

:I=+.>0,.$pPdPl7

Example:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

Could it be that this language doesn't always suck? I beat Jelly and MATL!

The test case with 5 is the longest and takes about 10 seconds on my machine.

This would be 12 bytes if $p was not bugged (we wouldn't need the >0,. part)

Explanation

Brachylog uses constraint logic programming by default for all integer arithmetic. Moreover, the labeling built-in = works on possibly infinite domains.

It successively unifies a variable with no constraints (i.e. in (-inf, inf)) as such: 0, 1, -1, 2, -2, 3, ….

Therefore, we can get the closest 7DP number by looking for the first number I unified in (-inf, inf) (using automatic backtracking), for which Input + I is a 7DP number.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Answer 3

Jelly, 17 bytes

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Works in theory, but takes many years to complete.

---

Here is a version that actually works for the given inputs, but theoretically fails for large inputs:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Try it here. This generates all primes up to 50, then finds all 7-combinations of primes in that list, and then all their products. Finally, it simply finds the closest element from that list to the given argument.

Of course, once our 7DPs contain primes higher than 50, this will fail. The theoretical version generates all primes up to 256n for an input n, but otherwise works the same way.

Proof

Let p(x) denote the next prime after x. An (extremely loose) upper bound for the closest 7DP product to x is:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

So we only need to check primes in [2…p(p(p(p(p(p(p(x)))))))]. Bertrand's postulate says that p(x) ≤ 2x, so it suffices to check all primes up to 128x.

Answer 4

MATL, 21 17 16 14 13 bytes

Thanks to Dennis for a suggestion that removed 4 bytes, and another that saved 1 more byte!

t17*Zq7XN!pYk

This works in theory, but runs out of memory for inputs above 6 (online compiler).

A more efficient version uses 21 bytes, and computes all test cases in about one second:

t3e4/k16+_YqZq7XN!pYk

Try it online!

• Memory-inefficient version
• Memory-efficient version
• Memory-efficient version, all test cases

Explanation

Memory-efficient version

Take input N = 860782 as an example. It suffices to consider primes up to M = 29, which is the first prime that multiplied by 2*3*5*7*11*13 exceeds N. In this example, 2*3*5*7*11*13*29 = 870870. The next prime is 31. Any product involving that prime or greater will be at least 2*3*5*7*11*13*31 = 930930, and so it's guaranteed not to be the solution, because it exceeds 870870 which exceeds N.

M is computed as the first prime greater than max(N/(2*3*5*7*11*13), 16). The max function is used for ensuring that at least 17 is picked. To save a few bytes, the code replaces 2*3*5*7*11*13 = 30030 by 30000, and function max by addition. These changes are valid because they give a larger value.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Memory-inefficient version

To further reduce the number of bytes the division can be removed; in fact, it suffices to multiply by 17 (thanks, @Dennis). This ensures that the next prime is included (by Bertrand's postulate) and that the result is at least 17. This works in theory, but runs out of memory for inputs larger than about 6.

In the code, the section

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

is replaced by

17*    % Multiply by 17

Answer 5

Pyke, 32 bytes

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Try it here!

Note this doesn't work online - it times out. This Version only checks for 2 distinct primes and should work faster. When there are 2 numbers of the same distance away from the target, it chooses the lower one.

This goes through all the numbers until it finds one that is bigger than the input and is a 7DP. For each number, it gets rid of it if it isn't a 7DP. It then has a list of 7DPs up to the input with one that is bigger. It then picks the one that is closest to the input.

Answer 6

Julia, 59 bytes

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

This is very inefficient, but it works for the first test case in practice and for the others in theory.

At the cost of 5 more bytes – for a total of 64 bytes – efficiency can be improved dramatically.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

Try it online!

Background

As mentioned in @LuisMendo's answer, the set of primes we have to consider for the nearest 7DP number is quite small. It suffices for the set to contains a 7DP number that is bigger than the input n, which will be true if and only if it contains a prime p &geq; 17 such that 30300p = 2·3·5·7·11·13·p &geq; n.

In On the interval containing at least one prime number proves that the interval [x, 1.5x) contains at least one prime number whenever x &geq; 8. Since 30030 / 16384 &approx; 1.83, that means there must be a prime p in (n/30030, n/16384) whenever n > 8 · 30300 = 242400.

Finally, when n < 510510, p = 17 is clearly sufficient, so we only need to consider primes up to n/16384 + 17.

At the cost of efficiency, we can consider primes up to 17n instead. This works when n = 1 and is vastly bigger than n/16384 + 17 for larger values of n.

How it works

17n|>primes and n>>14+17|>primes (the bitshift is equivalent to dividing by 2¹⁴ = 16384) compute the prime ranges mentioned in the previous paragraph. Then, combinations(...,7) computes all arrays of seven different prime numbers in that range, and mapping prod over those calculates their products, i.e., the 7DP numbers from which we'll choose the answer.

Next, -n subtracts n prom each 7DP number, then sort(...,by=abs) sorts those differences by their absolute values. Finally, we select the first difference with [] and compute the corresponding 7DP number by adding n with +n.

Answer 7

Pyth, 30 bytes

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

Try it online!

Test suite.

(5 takes too long to run)

Explanation

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Answer 8

05AB1E, 10 bytes

°Åp7.ÆPs.x

Try it online!

Tries all combinations of 7 of the first 10**input primes. Runs out of memory for inputs greater than 1.

Considerably more efficient 14 bytes version:

5°/7+Åp7.ÆPs.x

Try it online!

Uses the first (input / 100000 + 7) primes.

Answer 9

Mathematica 136 80 75 bytes

This is a straightforward approach, working outwards from n.

n is a 7-distinct-prime product iff the number of prime factors is 7 (PrimeNu@#==7) and none of these factors appears more than once (SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

My earlier submission (136 bytes) found both the first 7-distinct-prime product above n and, if it exists, the first 7-distinct-prime product below n. It then simply determined which was closer to n. If the products were equidistant, it returned both.

The current version checks n-1,n+1,n-2,n+2... until it reaches the first 7-distinct-prime product. This more efficient version adopts the approach Dennis took.

The key advance was in using ⌊k/2](-1)^k⌋ to return the series, 0, 1, -1, 2, -2... The zero is used to check whether n is itself a 7-distinct-prime product. For this reason, Floor(that is, ⌊...⌋) is used instead of Ceiling.

---

g[5]
g[860782]
g[1425060]

510510

870870

1438710