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

05AB1E, 6 bytes

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

---

Two 6 bytes alternatives provided by @Grimy:

GNfåP–

Try it online.

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

This one is very slow (the [2,5,7], 15 test case already times out), but less like the other two approaches:

sиPÑʒ›

Unlike the other two programs above, it takes the list as first input, and integer as second. It does include the optional 1 in the output as well, though.

Try it online.

s       # Swap so the stack is now [list-input, integer-input]
 и      # Repeat the list (flattened) the integer amount of times
        #  i.e. [2,5] and 10 → [2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5]
  P     # Take the product of this list
        #  → 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 these divisors:
     ›  #  And 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)

Answer 2

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

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 9

J, 24 bytes

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

Try it online!

Answer 10

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 11

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 12

Japt -f, 11 8 bytes

k
è@e!øV

Try it

Answer 13

Japt -f, 7 bytes

©k e!øV

Try it

Answer 14

Ruby -rprime, 61 bytes

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

Try it online!

Answer 15

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 16

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

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.