15
\$\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\$
  • 2
    \$\begingroup\$ Can you elaborate on the challenge? I don't understand it. Maybe explain the examples? \$\endgroup\$ – d-b Nov 3 '18 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 Nov 3 '18 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 Nov 3 '18 at 19:41
  • \$\begingroup\$ @d-b Factorize n into primes. If all of those primes are greater than B, n is B-rough. \$\endgroup\$ – Addison Crump Nov 3 '18 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 Nov 3 '18 at 20:30

11 Answers 11

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\$
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\$
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\$
  • 3
    \$\begingroup\$ Hmm, that assumption is probably verifiable, but an interesting problem nonetheless. I'll bounty for a proof. \$\endgroup\$ – Addison Crump Nov 3 '18 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 Nov 3 '18 at 10:59
  • 1
    \$\begingroup\$ @BlackOwlKai That sounds cool. See also math.stackexchange.com/questions/2983364/… \$\endgroup\$ – Anush Nov 5 '18 at 10:45
  • \$\begingroup\$ @Anush Sadly, my proof didn't work, because I made a mistake \$\endgroup\$ – Black Owl Kai Nov 5 '18 at 16:08
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\$
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\$
  • \$\begingroup\$ This can be simplified somewhat \$\endgroup\$ – H.PWiz Nov 3 '18 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 Nov 3 '18 at 12:57
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\$
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\$
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\$
  • \$\begingroup\$ What does all do? \$\endgroup\$ – Addison Crump Nov 3 '18 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 Nov 3 '18 at 7:10
  • \$\begingroup\$ @nwellnhof Wow! So that's what Junctions are useful for! \$\endgroup\$ – Jo King Nov 3 '18 at 10:56
  • \$\begingroup\$ Yes, note that you could also use [&] instead of all. \$\endgroup\$ – nwellnhof Nov 3 '18 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 Nov 3 '18 at 11:07
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\$
3
\$\begingroup\$

Jelly, 7 bytes

1Æf>Ạɗ#

Try it online!

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

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.