Function Repository Resource:

SmoothIntegerQ

Source Notebook

Test whether the prime factors of an integer are less than a given threshold

Contributed by: Kevin Reiss and Zachary Shelton

ResourceFunction["SmoothIntegerQ"][n,p]

returns True if there is no prime factor of n greater than p and False otherwise.

ResourceFunction["SmoothIntegerQ"][p]

represents an operator form of ResourceFunction["SmoothIntegerQ"] that can be applied to an integer.

Details

An integer is said to be p-smooth if its largest prime factor is less than or equal to p.
p can be any positive real; the largest prime less than or equal to p is used.
For negative integers n, n is considered p-smooth if Abs[n] is p-smooth.

Examples

Basic Examples (2) 

Show that 54 is 7-smooth:

In[1]:=
ResourceFunction["SmoothIntegerQ"][54, 7]
Out[1]=

54 is not 2-smooth, since its prime factors are 2 and 3:

In[2]:=
ResourceFunction["SmoothIntegerQ"][54, 2]
Out[2]=

Scope (2) 

The following is an operator which tests whether an integer is 7-smooth:

In[3]:=
ResourceFunction["SmoothIntegerQ"][7]
Out[3]=
In[4]:=
% /@ Range[50, 55]
Out[4]=

An integer is p-smooth for non-prime p if it is p-smooth for p being the greatest prime less than p:

In[5]:=
ResourceFunction["SmoothIntegerQ"][98, 7.7] == ResourceFunction["SmoothIntegerQ"][98, 7]
Out[5]=

π - smooth numbers are the same as 3-smooth numbers:

In[6]:=
AllTrue[Table[
  ResourceFunction["SmoothIntegerQ"][n, \[Pi]] == ResourceFunction["SmoothIntegerQ"][n, 3], {n, 1000}], TrueQ]
Out[6]=

Applications (1) 

Print the 7-smooth numbers less than or equal to 100:

In[7]:=
Select[Range[100], ResourceFunction["SmoothIntegerQ"][7]]
Out[7]=

Properties and Relations (3) 

A negative integer is considered smooth if its absolute value is smooth:

In[8]:=
ResourceFunction["SmoothIntegerQ"][-54, 7]
Out[8]=

Test that if n is 5-smooth, then so is -n for n up to 100:

In[9]:=
AllTrue[Table[
  ResourceFunction["SmoothIntegerQ"][n, 5] == ResourceFunction["SmoothIntegerQ"][-n, 5], {n, 100}], TrueQ]
Out[9]=

Any input besides an integer in the first argument gives False:

In[10]:=
ResourceFunction["SmoothIntegerQ"][E, 7]
Out[10]=
In[11]:=
ResourceFunction["SmoothIntegerQ"][x, 9]
Out[11]=

Negative values for the second input always return False:

In[12]:=
ResourceFunction["SmoothIntegerQ"][5, -7]
Out[12]=
In[13]:=
ResourceFunction["SmoothIntegerQ"][-7][100]
Out[13]=

Neat Examples (2) 

Calculate the number of "humble numbers" (7-smooth integers) with 1, 2, 3, 4 and 5 digits:

In[14]:=
{"Digits\[Rule]Count",
  Rule @@@ Tally[IntegerLength /@ Drop[Select[Range[10^5 - 1], ResourceFunction["SmoothIntegerQ"][7]], -1]] // Column} // Column
Out[14]=

123200 and 123201 comprise the largest consecutive pair that are both 13-smooth:

In[15]:=
{ResourceFunction["SmoothIntegerQ"][123200, 11], ResourceFunction["SmoothIntegerQ"][123201, 13]}
Out[15]=

Publisher

Kevin Reiss

Version History

  • 1.0.0 – 21 June 2021

Related Resources

Author Notes

This Function Repository submission was created live as a part of the Kevin + Zach livecoding series: Building a function the #WolframWay–YouTube.

License Information