17
\$\begingroup\$

from Wikipedia, a number is called B-powersmooth if all prime powers \$p^v\$ that divide the number satisfy \$p^v \leq B\$. B-powersmoothness is important, for example, for Pollard's p-1 factorization algorithm.

Task

your task is to get two numbers, \$n\$ and \$B\$, and output if \$n\$ is \$B\$-powersmooth.

Rules

  • You may take the input in any reasonable format
  • Since this is , the shortest code wins.
  • You can output a truthy/false value, or any two different values for true/false.
  • You can assume \$ 1 < B, n \$.

Test cases

n, b -> answer
3, 2 -> 0
10, 7 -> 1
123, 40 -> 0
123, 41 -> 1
64, 2 -> 0
64, 32 -> 0
64, 65 -> 1
720, 5 -> 0
720, 15 -> 0
720, 16 -> 1
20, 5 -> 1
\$\endgroup\$
7
  • \$\begingroup\$ Can we assume \$B \ge 1\$? \$\endgroup\$ – ovs Mar 31 at 7:44
  • 2
    \$\begingroup\$ Brownie points for beating my 5 bytes 05AB1E solution \$\endgroup\$ – Command Master Mar 31 at 11:59
  • 1
    \$\begingroup\$ @Deadcode thanks, I'll add those \$\endgroup\$ – Command Master Mar 31 at 19:13
  • 1
    \$\begingroup\$ Is this your solution? \$\endgroup\$ – Makonede Mar 31 at 19:34
  • 1
    \$\begingroup\$ @Makonede I had à@ in the end instead of @P, but it's about the same \$\endgroup\$ – Command Master Apr 1 at 4:17

19 Answers 19

9
\$\begingroup\$

J, 14 13 bytes

<[:>./2^/@p:]

Try it online!

-1 byte thanks to @Jonah

A dyadic function. The right argument is \$n\$, the left argument is \$B\$. Returns 0 if \$n\$ is \$B\$-powersmooth, 1 otherwise.

How it works

<[:>./2^/@p:]  NB. left arg = B, right arg = n
      2   p:]  NB. Prime factorization of n,
               NB. given as a 2-row matrix of [primes, exponents]
       ^/@     NB. Evaluate all pi^ei for each prime factor
 [:>./         NB. Maximum of all prime powers found above
<              NB. 1 if the above is greater than B, 0 otherwise
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Save 1 byte with <[:>./2^/@p:] \$\endgroup\$ – Jonah Mar 31 at 7:00
  • 1
    \$\begingroup\$ Save 1 byte with OR@:<2^/@p:] \$\endgroup\$ – FrownyFrog Apr 1 at 20:33
8
\$\begingroup\$

Regex (ECMAScript), 61 bytes

^(?=(|x*)\1*(?=\1\b)(?!(((x+)x+)(?=\3+,)\3*\4)\2+,)(x*)).*,\5

Try it online!

Takes \$n\$ and \$B\$ from input in unary as strings of xs whose length represents the number, separated by a ,.

Uses my prime power regex, and the same expression for cycling through divisors of N from largest to smallest as used in this problem.

# Take input as N in unary, followed by a comma, followed by B in unary
^
(?=
    (|x*)\1*(?=\1\b)  # cycle tail through all of the divisors of N, including N,
                      # from largest to smallest;
                      # \1 = the divisor, or zero if the divisor is N itself
    # Assert tail is a prime power
    (?!               # Assert that the following cannot match
        (             # Capture \2 to be the following:
            ((x+)x+)  # Cycle through all values of \4 and \3 such that \3 > \4 > 1
            (?=\3+,)  # such that \3 is a proper divisor of N
            \3*\4     # Cycle through all values of \2 > \3 that aren't divisible
                      # by \3, by letting \2 = \3 * A + \4 where A >= 0
        )
        \2+,          # where \2 is a proper divisor of N
    )
    (x*)              # \5 = the largest prime power factor of N
)
.*,                   # tail = B
\5                    # Assert that \5 <= B

Regex (ECMAScript), 61 59 bytes

Adapting Neil's idea of taking the arguments in \$(B,n)\$ order saves 2 bytes:

^(x*),(?!(x*)\2*(?=\2\b)(?!(((x+)x+)(?=\4+$)\4*\5)\3+$)x\1)

Try it online!
(For convenience, this test harness takes the arguments in \$(n,B)\$ order and passes them to the regex in reverse order.)

# Take input as B in unary, followed by a comma, followed by N in unary
^
(x*),                 # \1 = B; tail = N
(?!                   # Assert that the following cannot match
    (x*)\2*(?=\2\b)   # cycle tail through all of the divisors of N, including N;
                      # \2 = the divisor, or zero if the divisor is N itself
    # Assert tail is a prime power
    (?!               # Assert that the following cannot match
        (             # Capture \3 to be the following:
            ((x+)x+)  # Cycle through all values of \5 and \4 such that \4 > \5 > 1
            (?=\4+$)  # such that \4 is a proper divisor of N
            \4*\5     # Cycle through all values of \3 > \4 that aren't divisible
                      # by \4, by letting \3 = \4 * A + \5 where A >= 0
        )
        \3+$          # where \3 is a proper divisor of N
    )
    x\1               # Assert tail > B
)

Regex (ECMAScript 2018 / .NET), 54 52 bytes

-2 bytes by using Neil's idea but with the arguments in \$(n,B)\$ order

$(?<!^\4*(?!(((x+)x+)(?=\2+,)\2*\3)\1+,)(x+\5),(x+))

Try it online! - ECMAScript 2018
Try it online! - .NET

This works by first capturing \$B\$, then asserting that there does not exist any \$a>B\$ for which \$a\$ is a prime power that divides \$N\$.

# Take input as N in unary, followed by a comma, followed by B in unary
$                     # head = B
(?<!                  # Negative lookbehind; assert that it's not possible to find a
                      # match for the following. Evaluated from right-to-left, so read
                      # the inside of this from bottom to top (but go back to top-down
                      # order for reading inside the negative lookbehind)
    ^\4*              # Assert that \4 divides N
    # Assert tail is a prime power
    (?!               # Negative lookahead; assert that the following cannot match
        (             # Capture \1 to be the following:
            ((x+)x+)  # Cycle through all values of \3 and \2 such that \2 > \3 > 1
            (?=\2+,)  # such that \2 is a proper divisor of N
            \2*\3     # Cycle through all values of \1 > \2 that aren't divisible
                      # by \2, by letting \1 = \2 * A + \3 where A >= 0
        )
        \1+,          # where \2 is a proper divisor of N
    )    
    (x+\5)            # \4 = tail = any divisor of N greater than B; the "^\5*" above
                      #      asserts it to be a divisor of N. Note that in most regex
                      #      engines, putting the "^\5*" later than the negative
                      #      assertion, as is the case here, results in a slowdown, as
                      #      non-divisors of N will be tested for being prime powers.
    ,(x+)             # \5 = head = B
)
\$\endgroup\$
5
\$\begingroup\$

MATL, 6 bytes

&YF^<a

Inputs n then B.

Outputs 0 if n is B-powersmooth or 1 otherwise.

Try it online! Or verify all test cases

How it works

&YF  % Implicit input: n. Factorization with primes and exponents as separate outputs
^    % Element-wise power
<    % Implicit input: B. Less-than comparison, element-wise
a    % Any: gives true (1) if any value is nonzero, or false (0) otherwise
     % Implicit display
\$\endgroup\$
5
\$\begingroup\$

Brachylog, 5 bytes

ḋḅ∋×>

Try it online!

Takes \$n\$ through the input variable and \$B\$ through the output variable; fails if \$n\$ is \$B\$-powersmooth and succeeds if not.

 ḅ       Take the runs of consecutive equal elements from
ḋ        the prime factors of n.
  ∋      For some run,
   ×     the product of its elements
    >    is greater than B.
\$\endgroup\$
4
\$\begingroup\$

Factor + math.primes.factors, 37 bytes

[ group-factors unzip v^ supremum < ]

Try it online!

Explanation:

It's a quotation (anonymous function) that takes B and n (in that order) as input and returns a (flipped) boolean as output.

  • group-factors obtain the prime factorization of n as a sequence of pairs
  • unzip get the factors in one sequence and the exponents in another
  • v^ element-wise exponentiation of two vectors
  • supremum find the maximum value
  • < is B less than this value?
\$\endgroup\$
4
\$\begingroup\$

Husk, 8 7 bytes

≤⁰▲mΠgp

Try it online!

      p        # get the list of prime factors of arg2;
     g         # group equal ones together
   mΠ          # and multiply them together (to get the prime power divisors);
  ▲            # get the maximum of these;
≤⁰             # is it ≤ arg1?
\$\endgroup\$
3
\$\begingroup\$

Jelly, 7 bytes

ÆF*/€Ṁ>

Try it online!

Similar to Bubbler's answer. Returns a flipped boolean.

Explanation

ÆF*/€Ṁ< Main link: takes  n on the left, and B on the right
ÆF      prime factor and exponent pairs
  */€   reduce each by exponentiation
     Ṁ  maximum
      > greater than B?
\$\endgroup\$
1
  • 2
    \$\begingroup\$ < should be an equivalent of instead (or > to get a flipped boolean). \$\endgroup\$ – Bubbler Mar 31 at 6:45
3
\$\begingroup\$

Python 2, 68 bytes

The output is a positive integer for truthy cases and a 0 otherwise.

f=lambda n,b,p=2,m=1:b/m*(n<2or f(*[n/p,n,b,b,p,p+1,m*p][n%p>0::2]))

Try it online!

Commented:

f=lambda n,b,p=2,m=1:         # recursive function taking 4 arguments
                              # n, b - inputs from the challenge
                              # p=2  - candidate for a prime dividing n
                              # m=1  - a power of p dividing the original input n
b/m*( ... )                   # floor division, this is 0 if m>b
     n<2or ...                # if n==1, return True (1), else:
           f(*[ ... ][1::2])  # if n%p>0 (p does not divide n):
        == f(n,b,p+1)         #   try next p
           f(*[ ... ][0::2])  # if n%p==0 (p divides n):
        == f(n/p,b,p,m*p)     #   divide n by p, update power of p, m
\$\endgroup\$
3
\$\begingroup\$

Haskell, 108 107 bytes

1!_=[]
n!f|n`mod`f<1=f:(n`div`f)!f|x<-f+1=n!x
g(h:t)x|h`mod`x<1=h*x:t|1>0=x:h:t
n#b=all(<=b)$foldl g[1]$n!2

Try it online!

  • saved 1 thanks to @Unrelated String

  • ! finds all prime factors : it divides n by 2 while modulo is 0 then by 3, then by 4.. Wait 4 is not prime! Ah but it was already factorized by 2

  • g all that to group factors

  • # finally we return True if all are <= B

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

JavaScript (ES6),  53  52 bytes

Expects (b)(n). Returns 0 or true.

b=>g=(n,i=d=1)=>i>b?0:n%++d?d>n||g(n,1):g(n/d,i*d--)

Try it online!

Commented

b =>          // outer function taking b = powersmoothness rank
g = (         // recursive inner function taking:
  n,          //   n = input integer whose b-powersmoothness is tested
  i =         //   i = exponentiation of the current prime divisor,
              //       which must never exceed b
  d = 1       //   d = prime divisor candidate
) =>          //
i > b ?       // if i is greater than b:
  0           //   failure: stop and return 0
:             // else:
  n % ++d ?   //   increment d; if it's not a divisor of n:
    d > n     //     stop and return true if it's greater than n
    ||        //     otherwise:
      g(      //       do a recursive call:
        n,    //         pass n unchanged
        1     //         reset i to 1 while leaving d unchanged
      )       //       end of recursive call
  :           //   else (d is a prime divisor of n):
    g(        //     do a recursive call:
      n / d,  //       divide n by d
      i * d-- //       multiply i by d, decrement d afterwards
    )         //     end of recursive call
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 63 59 58 bytes

.+
$*
Mr`^\4*(?!(((1+)1+)(?=\2+¶)\2*\3)\1+¶)(1+\5)¶(1+)$
0

Try it online! Takes line-separated input n,B but test suite converts from comma-separated for convenience. Edit: Saved 1 byte thanks to a hint by @Deadcode. Explanation:

.+
$*

Convert n and B to unary.

Mr`^\4*(?!(((1+)1+)(?=\2+¶)\2*\3)\1+¶)(1+\5)¶(1+)$

Try to find (in $4) an integer that is greater than b, a power of a prime, and a factor of n. The r flag makes the expression match from the right, so $5 is matched to b first, then $4, then $4 is checked for the power of a prime (taken from @Deadcode's answer to Is it almost-prime?, matching left-to-right as it is a lookahead), then it is checked for a factor of n. The previous 63-byte version was faster because it checked for factors before prime powers: Try it online!

0

Check that there wasn't a match.

\$\endgroup\$
7
  • \$\begingroup\$ It's also 63 bytes with the arguments in non-reversed order and no need to logical-not the truthiness of the regex: Try it online! (this is just my ECMAScript 2018 regex) \$\endgroup\$ – Deadcode Mar 31 at 10:59
  • \$\begingroup\$ 60 bytes: Try it online! \$\endgroup\$ – Deadcode Mar 31 at 11:37
  • 1
    \$\begingroup\$ @Deadcode I found a better golf... slow though! \$\endgroup\$ – Neil Mar 31 at 12:15
  • \$\begingroup\$ Oh, nicely done! Why do I always forget to do that (?=A)(?!B)(?!B)A golf. At this point it's really rather ridiculous how many times I've forgotten to do it! \$\endgroup\$ – Deadcode Mar 31 at 17:08
  • 1
    \$\begingroup\$ @Deadcode You know what? I had previously investigated reversing my original 63-byte version, but because it costs a byte to reverse the match direction with the r flag, and I had a lookahead which would have turned into a lookbehind, it would still have been 63 bytes. But of course I've now eliminated the lookahead... I think your ^\5* needs to be ^\4* though. \$\endgroup\$ – Neil Mar 31 at 18:54
2
\$\begingroup\$

05AB1E, 5 bytes

Ties Unrelated String's Brachylog answer for #1.

ÒγP@P

Try it online!

ÒγP@P  # full program
    P  # product of...
       # (implicit) list of...
   @   # whether...
       # implicit input...
   @   # is greater than or equal to...
  P    # products of...
 γ     # consecutive runs of...
Ò      # prime factors of...
       # implicit input
       # implicit output
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 66 64 bytes

t;r;p;f(n,B){for(r=p=1;n/++p;r&=t/n<=B)for(t=n;n%p<1;n/=p);t=r;}

Try it online!

Takes two integers \$n\$ and \$B\$ as input and returns \$1\$ if \$n\$ is \$B\$-powersmooth or \$0\$ otherwise.

Explanation

t;r;p;f(n,B){                           // function taking two int inputs
                                        // n and B
             for(r=p=1;                 // loop over prime factors p of n
                                        // also init return value r to 1
                       n/++p;           // loop while p<=n also bump p
                             r&=t/n<=B) // at the end of each loop check that
                                        // the current prime power factor of
                                        // n (t/n) is less than or equal to B
                  for(                  // loop to strip n of all its
                                        // prime factors p
                      t=n;              // save copy of n in t before 
                                        // removing all p factors
                          n%p<1;        // loop while p is a factor of n
                                n/=p);  // reduce n by p  
             t=r;                       // return r  
}
\$\endgroup\$
1
\$\begingroup\$

Pyth, 24 23 bytes

FkrPE8 aY^@k1@k0;<eSYhE

Try it online!

Explanation

Fk    For loop with the iterator as k
E     Take first input.
PE    List of prime factors
rPE8  Run length encoding over the list, eg: [2, 2, 3] becomes [[2, 2], [1, 3]]
Y     Initialized to an empty list by default.
@k1   Element at index 1 of k.
@k0   Element at index 0 of k.
^     Apply exponentiation.
aY    Append element to Y
SY    Sort Y
e     Last element
hE    Take next input and increment by 1
<     Is it less than?
\$\endgroup\$
1
\$\begingroup\$

Ruby, 48 bytes

->n,b{(2..n).none?{|x|n/(n/=x while n%x<1;n)>b}}

Try it online!

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

JavaScript (Node.js), 76 bytes

n=>g=b=>{for(++b,p=1;b%++p;);for(q=b;q%p<1;q/=p);return n%b|q>1&&b<n&&g(b);}

Try it online!

Return false if n is B-powersmooth. Return 0 otherwise. (as per two different values rule)

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

Charcoal, 37 bytes

NθW¬⁼θΠυ⊞υ§Φ…·²θ¬﹪÷θ∨Πυ¹κ⁰¬›⌈EυXι№υιN

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for smooth, nothing if not. Explanation:

NθW¬⁼θΠυ⊞υ§Φ…·²θ¬﹪÷θ∨Πυ¹κ⁰

Input n and find its prime factors (taken from my answer to Zeroes at end of \$n!\$ in base \$m\$).

¬›⌈EυXι№υιN

Raise each prime factor to its multiplicity and compare the largest to B.

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

Excel, 149 bytes

=LET(q,SEQUENCE(A2),f,(MOD(A2,q)=0)*q,o,(MMULT(1*(MOD(f,TRANSPOSE(q))=0),q^0)=2)*f,p,FILTER(o,o),MAX((MMULT(1*(MOD(f,TRANSPOSE(p))=0),p^0)=1)*f)<=B2)

Explanation

=LET(                                        'function that allows variable assignment,
                                                 returns the value of the last parameter
q,SEQUENCE(A2)                               'q = list of numbers from 1 to n
f,(MOD(A2,q)=0)*q                            'f = if n mod q = 0 then q else 0
o,(MMULT(1*(MOD(f,TRANSPOSE(q))=0),q^0)=2)*f 'o = if f is prime then f else 0
         1*(MOD(f,TRANSPOSE(q))=0)           'matrix of f by q where 1 indicates f mod q = 0
                                   q^0       'vertical matrix of q 1's
   MMULT(                             )      'need to use matrix multiplication to sum  
                                                 each row inside a LET
                                       =2)*f 'if sum of the row is 2 (prime) then f else 0
p,FILTER(o,o)                                'p = all o where o <> 0
        1*(MOD(f,TRANSPOSE(p))=0)            'matrix of f by p where 1 indicates f mod p = 0
MAX((MMULT(                   ,p^0)=1*f)<=b2 'TRUE if largest f with one prime factor <= b

Spreadsheet

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

Orst, 18 bytes

κñˋςᏓ{ᏓĖΐÇ}Ñδ

Try it online!

As hex bytes, this is

DE 87 FF D0 E7 FF 47 FF A0 FF 47 18 DD 0E FF A5 2F D4

Encoding as UTF-8:

Þ‡ÿÐçÿGÿ ÿGÝÿ¥/Ô

How it works

κñˋςᏓ{ᏓĖΐÇ}Ñδ - Full program. Takes b, then a
κ             - Save b in variable $x
 ñˋ           - Remove and swap. Stack is [a]
   ςᏓ         - Base-and-powers; Prime decomposition of a
     {    }Ñ  - Over each pair:
      ᏓĖ      -   Reduce by power
        ΐ     -   Retrieve b
         Ç    -   Less than or equal?
            δ - True for all?
\$\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.