16
\$\begingroup\$

Background

A number n can be described as B-rough if all of the prime factors of n strictly exceed B.

The Challenge

Given two positive integers B and k, output the first k B-rough numbers.

Examples

Let f(B, k) be a function which returns the set containing the first k B-rough numbers.

> f(1, 10)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

> f(2, 5)
1, 3, 5, 7, 9

> f(10, 14)
1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59
\$\endgroup\$
10
  • 2
    \$\begingroup\$ Can you elaborate on the challenge? I don't understand it. Maybe explain the examples? \$\endgroup\$
    – d-b
    Commented Nov 3, 2018 at 17:41
  • \$\begingroup\$ I don't understand why you include 1 in all your answers when it's never greater than B? \$\endgroup\$
    – kamoroso94
    Commented Nov 3, 2018 at 17:56
  • 1
    \$\begingroup\$ 1 has no prime factors, so every prime factor of 1 is larger than B and 1 should appear in the output independent of B. \$\endgroup\$
    – Hood
    Commented Nov 3, 2018 at 19:41
  • \$\begingroup\$ @d-b Factorize n into primes. If all of those primes are greater than B, n is B-rough. \$\endgroup\$ Commented Nov 3, 2018 at 20:06
  • \$\begingroup\$ @AddisonCrump So for example, since the primes for 35 are 5 and 7, 35 is 4-rough? Is this some recognized common terminology? Never heard of it before. I still don't under the examples, especially not the last one. 14 numbers but what is 10?? \$\endgroup\$
    – d-b
    Commented Nov 3, 2018 at 20:30

12 Answers 12

5
\$\begingroup\$

Haskell, 53 44 bytes

b%k=take k[n|n<-[1..],all((>0).mod n)[2..b]]

Try it online!

Thanks to H.PWiz for -9 bytes!

b%k=                       -- given inputs b and k
 take k                    -- take the first k elements from 
  [n|n<-[1..]              -- the infinite list of all n > 0
   ,all            [2..b]] -- where all numbers from 2 to b (inclusive)
      ((>0).mod n)         -- do not divide n.
\$\endgroup\$
2
  • \$\begingroup\$ This can be simplified somewhat \$\endgroup\$
    – H.PWiz
    Commented Nov 3, 2018 at 12:47
  • \$\begingroup\$ @H.PWiz Right, somehow I only thought about taking the (>b)-part inside the comprehension (which does not work) but not the other way around. Thanks! \$\endgroup\$
    – Laikoni
    Commented Nov 3, 2018 at 12:57
5
\$\begingroup\$

Python 3, 80, 75 bytes

lambda B,k:[i for i in range(1,-~B*k)if all(i%j for j in range(2,B+1))][:k]

Try it online!

Thanks to shooqie for saving 5 bytes.

This assumes that the k'th B-rough number will never exceed \$B * k\$, which I don't know how to prove, but seems like a fairly safe assumption (and I can't find any counterexamples).

Alternate solution:

Python 2, 78 bytes

B,k=input()
i=1
while k:
 if all(i%j for j in range(2,B+1)):print i;k-=1
 i+=1

Try it online!

This solution does not make the above solution. And is much more efficient.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Hmm, that assumption is probably verifiable, but an interesting problem nonetheless. I'll bounty for a proof. \$\endgroup\$ Commented Nov 3, 2018 at 7:07
  • 1
    \$\begingroup\$ Why not lambda B,k:[i for i in range(1,-~B*k)if all(i%j for j in range(2,B+1))][:k] ? \$\endgroup\$
    – shooqie
    Commented Nov 3, 2018 at 10:59
  • 1
    \$\begingroup\$ @BlackOwlKai That sounds cool. See also math.stackexchange.com/questions/2983364/… \$\endgroup\$
    – user9207
    Commented Nov 5, 2018 at 10:45
  • \$\begingroup\$ @Anush Sadly, my proof didn't work, because I made a mistake \$\endgroup\$
    – Kateba
    Commented Nov 5, 2018 at 16:08
3
\$\begingroup\$

Jelly, 7 bytes

1Æf>Ạɗ#

Try it online!

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

Perl 6, 35 32 bytes

-3 bytes thanks to nwellnof!

{grep(*%all(2..$^b),1..*)[^$^k]}

Try it online!

An anonymous code block that takes two integers and returns a list of integers.

Explanation

{                              }  # Anonymous code block
 grep(             ,1..*)        # Filter from the positive integers
      *              # Is the number
       %             # Not divisible by
        all(      )  # All of the numbers
            2..$^b   # From 2 to b
                         [^$^k]   # And take the first k numbers
\$\endgroup\$
5
  • \$\begingroup\$ What does all do? \$\endgroup\$ Commented Nov 3, 2018 at 7:07
  • 1
    \$\begingroup\$ @AddisonCrump all checks if all the elements in the list are truthy. I will be adding an explanation for the whole thing shortly \$\endgroup\$
    – Jo King
    Commented Nov 3, 2018 at 7:10
  • \$\begingroup\$ @nwellnhof Wow! So that's what Junctions are useful for! \$\endgroup\$
    – Jo King
    Commented Nov 3, 2018 at 10:56
  • \$\begingroup\$ Yes, note that you could also use [&] instead of all. \$\endgroup\$
    – nwellnhof
    Commented Nov 3, 2018 at 10:57
  • \$\begingroup\$ @AddisonCrump I guess all isn't being used in that way any more, so I should update my answer. all creates a Junction of the values in the range 2..b, and any operations performed on the Junction gets performed on all the values simulataneously. When it is evaluated in Boolean context by the grep, this collapses into whether all the values in the Junction are truthy, ie non-zero \$\endgroup\$
    – Jo King
    Commented Nov 3, 2018 at 11:07
3
\$\begingroup\$

Husk, 9 8 bytes

↑foΛ>⁰pN

Try it online!

Takes \$B\$ as first and \$ k \$ as second input.

↑         -- take the first k elements 
       N  -- from the natural numbers
 f        -- filtered by
  o   p   -- the prime factors
   Λ>⁰    -- are all larger than the first input
\$\endgroup\$
2
\$\begingroup\$

Jelly, 10 bytes

1µg³!¤Ịµ⁴#

Try it online!

How it works

1µg³!¤Ịµ⁴#    Dyadic main link. Left = B, right = k
       µ⁴#    Take first k numbers satisfying...
  g             GCD with
   ³!¤          B factorial
      Ị         is insignificant (abs(x) <= 1)?
1µ            ... starting from 1.
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 33 bytes

NθNη≔⁰ζW‹Lυη«≦⊕ζ¿¬Φθ∧κ¬﹪ζ⊕κ⊞υζ»Iυ

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

NθNη

Input B and k.

≔⁰ζ

Set z to 0.

W‹Lυη«

Repeat until we have k values.

≦⊕ζ

Increment z.

¿¬Φθ∧κ¬﹪ζ⊕κ

Divide z by all the numbers from 2 to B and see if any remainder is zero.

⊞υζ»

If not then push z to the predefined empty list.

Iυ

Cast the list to string and implicitly output it.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 68 bytes

Takes input as (b)(k).

b=>k=>(o=[],n=1,g=d=>(d<2?o.push(n)==k:n%d&&g(d-1))||g(b,n++))(b)&&o

Try it online!

Commented

b => k => (             // input = b and k
  o = [],               // o[] = output array
  n = 1,                // n = value to test
  g = d => (            // g = recursive function, taking the divisor d
    d < 2 ?             // if d = 1:
      o.push(n) == k    //   push n into o[] and test whether o[] contains k elements
    :                   // else:
      n % d && g(d - 1) //   if d is not a divisor of n, do a recursive call with d - 1
    ) ||                // if the final result of g() is falsy,
    g(b, n++)           // do a recursive call with d = b and n + 1
)(b)                    // initial call to g() with d = b
&& o                    // return o[]
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 68 bytes

b=>g=(k,i=1,j=b)=>k?j>1?i%j?g(k,i,j-1):g(k,i+1):[i,...g(k-1,i+1)]:[]

Try it online!

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

APL(NARS), 52 chars, 104 bytes

r←a f w;i
r←,i←1⋄→3
i+←1⋄→3×⍳∨/a≥πi⋄r←r,i
→2×⍳w>↑⍴r

Above it seems the rows after 'r←a f w;i' have names 1 2 3;test:

  o←⎕fmt
  o 1 h 2
┌2───┐
│ 1 2│
└~───┘
  o 1 h 1
┌1─┐
│ 1│
└~─┘
  o 10 h 14
┌14───────────────────────────────────────┐
│ 1 11 13 17 19 23 29 31 37 41 43 47 53 59│
└~────────────────────────────────────────┘
 
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 9 bytes

∞ʒÒ¹›P}²£

Try it online or verify all test cases.

Explanation:

∞          # Infinite list starting at 1: [1,...]
 ʒ    }    # Filter it by:
  Ò        #  Get all prime factors of the current number
   ¹›      #  Check for each if they are larger than the first input
     P     #  And check if it's truthy for all of them
       ²£  # Leave only the leading amount of items equal to the second input
\$\endgroup\$
0
\$\begingroup\$

Ruby, 56 bytes

->b,k{(1..).lazy.reject{|n|
(2..b).any?{n%_1<1}}.take k}

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.