19
\$\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\$
  • \$\begingroup\$ Can we output in any order? \$\endgroup\$ – xnor Sep 13 at 2:25
  • \$\begingroup\$ @xnor Yes, output in any order is fine. \$\endgroup\$ – AdmBorkBork Sep 13 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 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 at 19:03
  • \$\begingroup\$ @AZTECCO Right. But, for example, if your list is [2, 3, 7] you can't use 5. \$\endgroup\$ – AdmBorkBork Sep 16 at 12:35

19 Answers 19

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 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)
\$\endgroup\$
  • 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\$ – Grimy Sep 12 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\$ – Kevin Cruijssen Sep 12 at 13:50
  • 1
    \$\begingroup\$ For vertical output: GNfåP– \$\endgroup\$ – Grimy Sep 12 at 13:55
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\$

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\$
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 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\$
  • \$\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 at 2:47
  • \$\begingroup\$ @xnor Thanks for the improvement. Your approach is quite good as well. \$\endgroup\$ – Joel Sep 13 at 2:57
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\$
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\$
  • \$\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 at 10:12
  • \$\begingroup\$ Since, e.g., 2**0 = 1, you can optionally include 1 in your output list \$\endgroup\$ – Embodiment of Ignorance Sep 14 at 3:46
  • \$\begingroup\$ That was not a part of the original spec. \$\endgroup\$ – Shaggy Sep 14 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\$
  • \$\begingroup\$ Thanks but.. how does it work? \$\endgroup\$ – AZTECCO Sep 19 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 at 17:45

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.