Some Prime Peerage

Question

(Randomly inspired by https://mathoverflow.net/q/339890)
(Related: 1, 2)

Given an input list of distinct prime numbers (e.g., [2, 5, 7]), and a integer n, output all positive integers strictly smaller than n that contain only those primes as divisors. For input [2, 5, 7] and n=15 this means an output of [2, 4, 5, 7, 8, 10, 14].

Further Examples

[list] n | output

[2, 5, 7] 15 | [2, 4, 5, 7, 8, 10, 14]
[2, 5, 7] 14 | [2, 4, 5, 7, 8, 10]
[2] 3 | [2]
[2] 9 | [2, 4, 8]
[103, 101, 97] 10000 | [97, 101, 103, 9409, 9797, 9991]
[97, 101, 103] 104 | [97, 101, 103]

Rules and Clarifications

• The input list is guaranteed non-empty, but may be only a single element
• You can assume the input list is pre-sorted in whatever way is most convenient
• n will always be larger than the largest element in the input list
• Since, e.g., 2**0 = 1, you can optionally include 1 in your output list
• Input and output can be given by any convenient method
• You can print the result to STDOUT or return it as a function result
• Either a full program or a function are acceptable
• If applicable, you can assume the input/output integers fit in your language's native int range
• Standard loopholes are forbidden
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins

Answer 1

Stax, 6 bytes

Ç─☼?▬µ

Run and debug it at staxlang.xyz!

Unpacked (7 bytes) and explanation:

vf:Fn-!
vf         Filter range [1..n-1]:
  :F         Distinct prime factors
    n-       Remove all in provided list
      !      Is empty?

Answer 2

05AB1E, 6 5 bytes

PmÑʒ›

-1 byte thanks to @ovs (and @Grimmy, who provided sиPÑʒ› as 6 bytes alternative initially).

Takes the list as first input, and integer as second. Includes the optional 1 in the output.
Extremely slow approach (the [2,5,7], 15 test case already times out).

Try it online. (No test suite, because it's too slow for most.)

Explanation:

P      # Take the product of the (implicit) input-list
       #  i.e. [2,5] → 10
 m     # Take the (implicit) input-integer to the power this product
       #  i.e. 10 → 10000000000
  Ñ    # Get all divisors of this integer
       # (the bottleneck for larger integers in this approach)
       #  → [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250,256,320,400,500,512,625,640,800,1000,1024,1250,1280,1600,2000,2500,2560,3125,3200,4000,5000,5120,6250,6400,8000,10000,12500,12800,15625,16000,20000,25000,25600,31250,32000,40000,50000,62500,64000,78125,80000,100000,125000,128000,156250,160000,200000,250000,312500,320000,390625,400000,500000,625000,640000,781250,800000,1000000,1250000,1562500,1600000,1953125,2000000,2500000,3125000,3200000,3906250,4000000,5000000,6250000,7812500,8000000,9765625,10000000,12500000,15625000,16000000,19531250,20000000,25000000,31250000,39062500,40000000,50000000,62500000,78125000,80000000,100000000,125000000,156250000,200000000,250000000,312500000,400000000,500000000,625000000,1000000000,1250000000,2000000000,2500000000,5000000000,10000000000]
   ʒ   # Filter this list of divisors:
    ›  #  Only keep those where the (implicit) input-integer is larger than the divisor
       #  → [1,2,4,5,8]
       # (after the filter, the result is output implicitly)

---

Two faster 6 bytes alternatives:

<LʒfåP

Takes the integer as first input, list as second. Includes the optional 1 in the output.

Try it online or verify all test cases.

Explanation:

<       # Decrease the (implicit) input by 1
 L      # Create a list in the range [1,input-1]
  ʒ     # Filter it by:
   f    #  Get all prime factors of the current number (without duplicates)
    å   #  Check for each if its in the (implicit) input-list
     P  #  And check if this is truthy for all
        # (after the filter, the result is output implicitly)

---

Thanks to @Grimmy:

GNfåP–

Try it online or verify all test cases.

G       # Loop `N` in the range [1, (implicit) input):
 Nf     #  Get all prime factors of `N` (without duplicates)
   å    #  Check for each if its in the (implicit) input-list
    P   #  And check if this is truthy for all
     –  #  If it is, output the current `N` with trailing newline

Answer 3

JavaScript (ES6),  64 ... 52  50 bytes

Takes input as (n)(primes) where primes is a set. Outputs by modifying the set.

n=>g=(s,q=1)=>{for(p of s)(p*=q)<n&&g(s.add(p),p)}

Try it online!

Commented

n =>              // n = maximum value
g = (             // g is a recursive function taking:
  s,              //   s = set of primes
  q = 1           //   q = current product, initialized to 1
) => {            //
  for(p of s)     // for each value p in s:
    (p *= q)      //   multiply p by q
    < n &&        //   if the result is less than n:
      g(          //     do a recursive call:
        s.add(p), //       with p added to the set
        p         //       with q = p
      )           //     end of recursive call
}                 //

Answer 4

Python 3, 68 65 bytes

f=lambda s,n,c=1:n//c*s and f(s,n,s[0]*c)+f(s[1:],n,c)or[c][:c<n]

Try it online!

-3 bytes thanks to @xnor

The function takes a prime sequence and an integer n as inputs. The output is a list that includes 1.

Ungolfed:

def f(s, n, c=1):
    if not c < n:
       return []
    elif not s:
       return [c]
    else:
       return f(s,n,s[0]*c) + f(s[1:],n,c)

Try it online!

Answer 5

Haskell, 51 bytes

For each prime x in the list of primes p the expression mapM((<$>[0..n]).(^))p computes all powers \$1,x,x^2,\ldots,x^n\$ (where \$n\$ is the second input just used as an upper bound) and then the cartesian product of all these sequences. After that we compute the product of all entries of this cartesian product and filter out all that are too large.

This means that it is incredibly slow or might even crash if n is large or the list of primes p is large, as this cartesian product contains \$(\#p)^n\$ entries.

p#n=[k|k<-product<$>mapM((<$>[0..n]).(^))p,k<n,k>1]

Try it online!

Answer 6

Haskell, 39 bytes

l%n=[k|k<-[2..n-1],mod(product l^k)k<1]

Try it online!

Checks if k is divisible only by primes in l by seeing if the product of l taken to a high power is divisible by k.

Answer 7

Python 2, 65 bytes

lambda l,n:[k for k in range(2,n)if reduce(int.__mul__,l)**n%k<1]

Try it online!

Checks if k is divisible only by primes in l by seeing if the product of l taken to a high power is divisible by k.

If l can be taken as a list of strings eval("*".join(l)) saves 3 bytes over reduce(int.__mul__,l) and can be used in Python 3 which lacks reduce.

Python 3, 64 bytes

def f(l,n,P=1):
 for x in l:P*=x
 n-=1;P**n%n or print(n);f(l,n)

Try it online!

A function the prints in reverse order and terminates with error.

The recursive solution below would be shorter if n itself were included in the list. I tried recursively computing the product of l as well, but that was longer.

62 bytes (non-working)

f=lambda l,n:n*[f]and[n][reduce(int.__mul__,l)**n%n:]+f(l,n-1)

Try it online!

Answer 8

APL (Dyalog Unicode), 25 bytes ^SBCS

{⍺{v/⍨⍺>v←∪,∘.×⍨⍵}⍣⍺⊢1,⍵}

Try it online!

How it works:

The main idea of this solution is that we take the input primes ⍵, we prepend 1 to them with 1,⍵ and we multiply these numbers all together a bunch of times, where "a bunch of times" is the n input (refered to by ⍺). This repetition is controlled by ⍣⍺. What we actually repeat is the inner dfn

{v/⍨⍺>v←∪,∘.×⍨⍵}

This dfn takes as ⍺ the input n and as ⍵ the multiplications we have so far. Then, ∘.×⍨⍵ multiplies all those accumulated multiplications so far with themselves, into a matrix that looks like a "times table" of ⍵ with itself.

Then ∪, flattens and removes duplicates and assigns that to v with v←.

Finally, v/⍨⍺>v filters out elements greater than or equal to ⍺, which is the n input.

Answer 9

Gaia, 10 bytes

…@e⟪ḍ‡⁻!⟫⁇

Try it online!

I've never used ‡ with a monad before, it's quite helpful for stack manipulation.

…		| push [0..n-1]
@e		| push list of primes
  ⟪    ⟫⁇	| filter [0..n-1] for where the following predicate is true:
   ḍ‡		| the list of prime factors
     ⁻		| minus the list of primes
      !		| is empty

Answer 10

J, 24 bytes

(]#~0=1#.(-."1~q:))2}.i.

Try it online!

Answer 11

Jelly, 7 bytes

ṖÆffƑ¥Ƈ

Try it online!

A dyadic link taking the exclusive upper bound as its left argument and the list of primes as its right. Returns a list that includes 1 as well as the numbers only composed of the supplied primes.

An alternative 7 would be ṖÆfḟ¥Ðḟ

Answer 12

Python 2, 98 bytes

lambda a,n:[i for i in R(2,n)if{p for p in R(2,i+1)if(i%p<1)*all(j%p for j in R(2,p))}<=a]
R=range

Try it online!

Answer 13

Japt -f, 11 8 bytes

k
è@e!øV

Try it

Answer 14

Japt -f, 7 bytes

©k e!øV

Try it

Answer 15

Ruby -rprime, 61 bytes

->n,l{(2..n).select{|i|i.prime_division.all?{|b,|[b]-l==[]}}}

Try it online!

Answer 16

Retina 0.8.2, 64 bytes

\d+
$*
\G1
$.`,$`;
+`,(1+)(\1)*(?=;.* \1\b)
,1$#2$*
!`\d+(?=,1;)

Try it online! List includes smaller test cases (10000 times out because of all the long strings). Takes input in the order n f1 f2 f3... (factors do not need to be prime but they do need to be coprime). Output includes 1. Explanation:

\d+
$*

Convert to unary.

\G1
$.`,$`;

Generate a list from 0 to n-1, in both decimal and unary.

+`,(1+)(\1)*(?=;.* \1\b)
,1$#2$*

Repeatedly divide the unary by any available factors.

!`\d+(?=,1;)

Output the decimal numbers where the unary number has been reduced to 1.

Answer 17

Pyth, 10 bytes

f!-PThQtUe

Try it online!

Takes input as [[primes...], n]

        Ue  # range(0, Q[-1])  (Q is the input, implicit)
       t    #                [1:] -> range(1, Q[-1]), tUe == PSe
f           # filter that on the condition: lambda T:
   PT       # prime_divisors(T)
  -  hQ     #                   - Q[0]
 !          # logical negation (![] == True)

Answer 18

Perl 6, 27 bytes

{grep [*](@^a)**$^b%%*,^$b}

Try it online!

Port of xnor's Haskell solution. Also outputs 1.

Answer 19

Charcoal, 22 20 bytes

ＩΦ…²η⬤…·²ι∨﹪ιλ⊙θ¬﹪λν

Try it online! Link is to verbose version of code. Too slow for the larger test case. Explanation:

 Φ                      Filter on
  …                     Range from
   ²                    Literal `2` to
    η                   Input limit
     ⬤                  Where all values
      …·                Inclusive range from
        ²               Literal `2` to
         ι              Filter value
          ∨             Either
             λ          Inner value
           ﹪            Is not a divisor of
            ι           Filter value
              ⊙         Or any of
               θ        Input primes
                   ν    Current prime
                ¬﹪      Is a divisor of
                  λ     Inner value
Ｉ                       Cast to string for implicit print

Previous faster 22-byte answer:

⊞υ¹ＦυＦ×ιθＦ›‹κη№υκ⊞υκＩυ

Try it online! Link is to verbose version of code. Output includes 1. Explanation:

⊞υ¹

Push 1 to the predefined empty list.

Ｆυ

Loop over the list, including any items pushed to it during the loop.

Ｆ×ιθ

Multiply the current item by each prime and loop over the products.

Ｆ›‹κη№υκ

Check whether the product is a new value.

⊞υκ

If so then push it to the list.

Ｉυ

Print the list.

Answer 20

C (clang), 115 bytes

#define f(n,l,z){int j,i,k,x[n]={};for(i=x[1]=1;i<n;printf(x[i]+"\0%d ",i++))for(j=z;j--;k<n?x[k]=x[i]:0)k=i*l[j];}

Try it online!

A Sieve of Eratosthenes based solution.

(Includes 1 in the output)

Thanks to @ceilingcat suggestion : printf(x[i]+"\0%d ",i++) instead of x[i]&&printf("%d ",i),i++ I suppose it shifts the pointer of the literal but didn't found any documentation, if anyone can give me some insights it would be welcome.

Answer 21

Husk, 8 bytes

fȯ¦⁰upŀ²

Try it online!