25
\$\begingroup\$

(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 so all usual golfing rules apply, and the shortest code (in bytes) wins
\$\endgroup\$
6
  • \$\begingroup\$ Can we output in any order? \$\endgroup\$
    – xnor
    Sep 13, 2019 at 2:25
  • \$\begingroup\$ @xnor Yes, output in any order is fine. \$\endgroup\$ Sep 13, 2019 at 12:28
  • \$\begingroup\$ Excuse me.. Just to be absolutely sure: "that contain only those primes as divisors" means "that contains only at least one of those primes as prime divisors"? \$\endgroup\$
    – AZTECCO
    Sep 13, 2019 at 21:05
  • \$\begingroup\$ You should have informed the existing solutions of the change to the spec to allow 1 in the output. \$\endgroup\$
    – Shaggy
    Sep 14, 2019 at 19:03
  • \$\begingroup\$ @AZTECCO Right. But, for example, if your list is [2, 3, 7] you can't use 5. \$\endgroup\$ Sep 16, 2019 at 12:35

21 Answers 21

5
\$\begingroup\$

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

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Alternative 7: sиPѦʒ›. I thought I had a 6, but there doesn't seem to be a way around using s/I/¹ \$\endgroup\$
    – Grimmy
    Sep 12, 2019 at 13:44
  • \$\begingroup\$ @Grimy Nice alternative, but that sure takes a long long time to execute, though. For first test case it has to find all divisors of 4747561509943000000000000000. ;) \$\endgroup\$ Sep 12, 2019 at 13:50
  • 1
    \$\begingroup\$ For vertical output: GNfåP– \$\endgroup\$
    – Grimmy
    Sep 12, 2019 at 13:55
  • 1
    \$\begingroup\$ For the last approach PmÑʒ› works at 5 bytes. \$\endgroup\$
    – ovs
    Oct 21, 2020 at 13:00
  • \$\begingroup\$ @ovs Thanks! Pretty logical now that I see it, but well done coming up with it. :) \$\endgroup\$ Oct 21, 2020 at 13:22
4
\$\begingroup\$

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ That's some neat short-circuiting code you have. It looks like you can combine the first two conditions as c*s<n*s. Edit: n//c*s is shorter. \$\endgroup\$
    – xnor
    Sep 13, 2019 at 2:47
  • \$\begingroup\$ @xnor Thanks for the improvement. Your approach is quite good as well. \$\endgroup\$
    – Joel
    Sep 13, 2019 at 2:57
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
+100
\$\begingroup\$

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.

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

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

J, 24 bytes

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

Try it online!

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

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ḟ¥Ðḟ

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

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!

\$\endgroup\$
0
\$\begingroup\$

Japt -f, 11 8 bytes

k
è@e!øV

Try it

\$\endgroup\$
0
\$\begingroup\$

Japt -f, 7 bytes

©k e!øV

Try it

\$\endgroup\$
3
  • \$\begingroup\$ This includes 1 in the output, which it shouldn't. I started with k e!øV for my solution too but needed the 2 extra bytes to filter 0 & 1. \$\endgroup\$
    – Shaggy
    Sep 13, 2019 at 10:12
  • \$\begingroup\$ Since, e.g., 2**0 = 1, you can optionally include 1 in your output list \$\endgroup\$
    – Gymhgy
    Sep 14, 2019 at 3:46
  • \$\begingroup\$ That was not a part of the original spec. \$\endgroup\$
    – Shaggy
    Sep 14, 2019 at 19:02
0
\$\begingroup\$

Ruby -rprime, 61 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

Perl 6, 27 bytes

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

Try it online!

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

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 22 20 bytes

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

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
I                       Cast to string for implicit print

Previous faster 22-byte answer:

⊞υ¹FυF×ιθF›‹κη№υκ⊞υκIυ

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

⊞υ¹

Push 1 to the predefined empty list.

Fυ

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

F×ιθ

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

F›‹κη№υκ

Check whether the product is a new value.

⊞υκ

If so then push it to the list.

Iυ

Print the list.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks but.. how does it work? \$\endgroup\$
    – AZTECCO
    Sep 19, 2019 at 3:31
  • 1
    \$\begingroup\$ If x[i]==1 then the string is "%d ". If x[i]==0 then the string is "". C strings are null terminated so an explicit null character terminates the string. This hack also abuses some undefined behavior in clang related to the i++. \$\endgroup\$
    – ceilingcat
    Sep 19, 2019 at 17:45
0
\$\begingroup\$

Husk, 8 bytes

fȯ¦⁰upŀ²

Try it online!

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