# Check B-powersmoothness

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.

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

• Can we assume $B \ge 1$?
– ovs
Mar 31, 2021 at 7:44
• Brownie points for beating my 5 bytes 05AB1E solution Mar 31, 2021 at 11:59
• Is this your solution? Mar 31, 2021 at 19:34
• @Makonede I had à@ in the end instead of @P, but it's about the same Apr 1, 2021 at 4:17

# 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

• Save 1 byte with <[:>./2^/@p:] Mar 31, 2021 at 7:00
• Save 1 byte with OR@:<2^/@p:] Apr 1, 2021 at 20:33

# 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
# 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
)


# MATL, 6 bytes

&YF^<a


Inputs n then B.

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

### 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


# 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.


# 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?

# 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?


# 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?

• < should be an equivalent of ≤ instead (or > to get a flipped boolean). Mar 31, 2021 at 6:45

# 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


1!_=[]
n!f|nmodf<1=f:(ndivf)!f|x<-f+1=n!x
g(h:t)x|hmodx<1=h*x:t|1>0=x:h:t
n#b=all(<=b)$foldl g$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

# 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


# Retina 0.8.2, 6359 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.

• 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) Mar 31, 2021 at 10:59
• 60 bytes: Try it online! Mar 31, 2021 at 11:37
• @Deadcode I found a better golf... slow though!
– Neil
Mar 31, 2021 at 12:15
• 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! Mar 31, 2021 at 17:08
• @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.
– Neil
Mar 31, 2021 at 18:54

# 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


# 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
}


# 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?


# Ruby, 48 bytes

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


Try it online!

# 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)

# Charcoal, 37 bytes

ＮθＷ¬⁼θΠυ⊞υ§Φ…·²θ¬﹪÷θ∨Πυ¹κ⁰¬›⌈ＥυＸι№υιＮ


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

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


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

¬›⌈ＥυＸι№υιＮ


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

# 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


# 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?