59
\$\begingroup\$

Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest.

A smooth number is one whose largest prime factor is small. Numbers of this type are useful for the fast Fourier transform algorithm, cryptanalysis, and other applications.

For instance, over the range 5, 6, 7, 8, 9, 10, 8 is the smoothest number, because 8's greatest prime factor is 2, whereas all of the other numbers have a prime factor of 3 or greater.

Input: The input will be two positive integers, which define a range. The minimum allowable integer in the range is 2. You may choose whether the range is inclusive, exclusive, semi-exclusive, etc, as long as an arbitrary range can be specified within the bounds of your language. You may take the numbers via function input, stdin, command line argument, or any equivalent method for your language. No encoding extra information in the input.

Output: Return, print or equivalent one or more integers in the input range which are maximally smooth (minimal greatest factor). Returning multiple results is optional, but if you choose to do so the results must be clearly delimited. Native output format is fine for multiple results.

Please state in your answer how you are taking input and giving output.

Scoring: Code golf. Count by characters if written in ASCII, or 8*bytes/7 if not in ASCII.

Test cases:

Note: These are Python-style ranges, including the low end but not the high end. Change as appropriate to your program. Only one result is necessary.

smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002
\$\endgroup\$
  • \$\begingroup\$ Are ranges specified as (start,length) instead of (start,end) acceptable? \$\endgroup\$ – CodesInChaos Aug 21 '14 at 16:26
  • 1
    \$\begingroup\$ @CodesInChaos Sure. It's covered under the "or whatever" clause. \$\endgroup\$ – isaacg Aug 21 '14 at 17:09
  • 3
    \$\begingroup\$ I don't see the point in penalizing non-ASCII answers. It would be simpler to just count bytes in all cases. \$\endgroup\$ – nyuszika7h Aug 21 '14 at 17:59
  • 1
    \$\begingroup\$ @nyuszika7h Ascii is significantly smaller than a byte - it only uses 7 bits. Therefore, I denote one character by 7 bits, and scale other languages accordingly. However, if the language is non-ASCII but can pack all of its characters into 7 bits, I will not apply the surcharge. See J/K vs. APL. tl;dr Bytes is simpler, but gives APL et. al. a subtle but unfair advantage. \$\endgroup\$ – isaacg Aug 21 '14 at 18:31
  • 3
    \$\begingroup\$ @isaacg you're encouraging the creation of pseudo-languages using smaller character sets. if we score 7-bit character sets different from 8-bit character sets, someone can pack most modern languages into 6 bits (64 characters gets us A-Z, 0-9, a handful of whitespace, 20 punctuation, and a few to spare). \$\endgroup\$ – Sparr Mar 8 '15 at 7:14

39 Answers 39

1
\$\begingroup\$

Whispers v2, 183 bytes

> Input
> Input
>> 1…2
>> ∤L
>> L’
>> Each 4 3
>> Select∧ 5 L
>> Each 7 6
>> Lⁿ10
> -1
>> Each 9 8
>> L‖R
>> Each 12 11 3
>> 13ᴺ
>> Each 9 14
> 0
>> 15ⁿ16
>> Output 17

Try it online!

Aside from revamping the algorithm, the only real golfing opportunity can be found on lines 9 and 10, but swapping them. When they're the other way round, the code is 1 byte longer, due to the repeated use of 9 or 10.

The structure tree for this program is:

tree

Red represents nilad lines, green represents function arguments. Arrows from \$a \to b\$ show the use of line \$a\$ as an argument for line \$b\$.

How it works.

We start at lines 1, 2 and 3. The first two simply take and store the inputs \$\alpha\$ and \$\beta\$ on lines 1 and 2 respectively. There two values are then passed to line 3, 1…2, which form the range

$$R := [\alpha, \alpha+1, ..., \beta-1, \beta]$$

As you can see from the tree above, \$R\$ is used in two places: line 6 and line 13. As line 6 eventually leads to line 13, we'll take the path down 6.

Line 6 is an Each statement, that maps a function (the first line reference) over an array (the second line reference). Here, the function is defined on line 4 as \$f(x) = \{i \: | \: (i | x), (i \le x), i \in \mathbb{N}\}\$ i.e. the array of \$x\$'s divisors. The array is \$R\$, so line 6 iterates over \$R\$, returning the divisors of each integer, forming a new array

$$D := [f(\alpha), f(\alpha+1), ..., f(\beta-1), f(\beta)]$$

We then get more complicated as we skip down to line 8. Line 8 is also an Each statement, but its function argument, line 7 is split over two lines, 7 and 5:

>> L’
>> Select∧ 5 L

Mathematically, this is the function \$g(A) = \{i \: | \: (i \in \mathbb{P}), (i \in A)\}\$, that takes a set \$A\$ and returns all the primes in \$A\$. Line 8 is iterating over \$D\$, essentially filtering all composite numbers from each subarray in \$D\$, to form

$$A := [g(f(\alpha)), g(f(\alpha+1)), ..., g(f(\beta-1)), g(f(\beta))]$$

Then, we encounter yet another Each statement on line 11, which iterates line 9 over \$A\$. Line 9 takes an array and returns the final element of that array. As \$g(A)\$ returns the array sorted, this is equivalent to return the largest value in that array. At this point, we remember that \$g(f(x))\$ returns the list of prime factors of \$x\$, so line 9 maps each \$x\$ to its largest prime factor, returning

$$B := [\max(g(f(\alpha))), \max(g(f(\alpha+1))), ..., \max(g(f(\beta-1))), \max(g(f(\beta)))]$$

Once we have \$B\$, we now have an array we can sort \$R\$ by, e.g. we sort each value \$x\$ in \$R\$ by the resulting value of \$\max(g(f(x)))\$. However, we do not have a sort-by command in Whispers, only the simple Python sort(list). Luckily, due to how sort sorts lists of lists, we can concatenate each \$x\$ with \$\max(g(f(x))\$ and sort by the first element, what Python does naturally.

Lines 12 and 13 perform this concatenation, by iterating a concatenate function (line 12) over \$B\$ and \$R\$. This forms an array of pairs of numbers, in the form \$[\max(g(f(x))), x]\$. Next, we sort this array on line 14, which, due to the way Python compares lists, places the numbers with the lowest largest prime factor towards the end.

Almost finished. The only things left to do are to extract \$R\$, sorted by \$B\$ (we'll call this array \$R_B\$. This is done simply by taking the last element of each subarray (line 9 already does this for us, so we simply need Each 9 14 on line 15, rather than defining a new function). Once that's done, we simply take the first element in \$R_B\$, which will be (one of) the number with the lowest largest prime factor i.e. the smoothest number.

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

Brachylog, 5 bytes

⟦₃ḋᵒh

Try it online!

Takes input as a list of two (or more, actually) values in no particular order, and outputs a single value through the output variable of the predicate (if you try to run it as a full program, it'll just print true. at you, unless you stick a w on the end). The input is interpreted as a Python-style range because to feed multiple values I need to give it a subscript no matter whether it's , , or so I may as well choose the one that matches the test cases.

    h The first item of
⟦₃    the range represented by the input
   ᵒ  after it's been sorted by
  ḋ   prime factorization.

Saves three bytes over the more obvious ⟦₃{ḋh}ᵒh by taking advantage of that Brachylog sorts its lists by elements first rather than lengths, such that the first step of sorting by prime factorizations is sorting by largest prime factors.

\$\endgroup\$
0
\$\begingroup\$

C#, 240 234 226 161 characters


int S(int i,int b){int s=2<<29,n=0,k,j,p;for(k=i;i<b;k=++i){for(;k>1;--k){if(i%k<1){p=1;for(j=2;j<k;++j)if(k%j<1)p=0;if(p>0)break;}}if(k<s){s=k;n=i;}}return n;}}


Acknowledgements & Reduction Explanations
- Thanks to CodesInChaos for reductions to 226, see comments for specifics
- Reduced to 161 after re-reading the rules and seeing that a mere function is allowed (i.e., a free-standing program is not required.)

Usage
function:
- input: two integers
- output: if multiple valid answers exist, returns the smallest


Explanation (with comments and runnable test-wrapper)

class Test
{
    int S(int i, int b)
    {
        //s = lowest gpf found so far
        //n = best answer so far
        //i = range iterator
        //p = prime indicator (1=true, 0=false)
        int s = 2 << 29, n = 0, k, j, p;
        for(k=i; i<b; k=++i)
        {
            //iterate through the factors of i
            for(;k>1;--k)
            {
                if (i % k < 1)
                {
                    p=1;
                    //determine if k is prime
                    for (j = 2; j < k; ++j)
                        if (k % j < 1)
                            p = 0;
                    if (p>0) break;
                }
            }
            if (k < s)
            {
                s = k;
                n = i;
            }
        }
        return n;
    }

    public static void Main(string[] args)
    {
        var d = new D();
        System.Diagnostics.Debug.Assert(d.S(5, 11) == 8);
        System.Diagnostics.Debug.Assert(d.S(9, 16) == 9);
        System.Diagnostics.Debug.Assert(d.S(9, 17) == 16);
        System.Diagnostics.Debug.Assert(d.S(157, 249) == 162);
        System.Diagnostics.Debug.Assert(d.S(2001, 2014) == 2002);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Why using System? As far as I can tell, you're only using it once, a qualified name System.Console.Write should be shorter. \$\endgroup\$ – CodesInChaos Aug 21 '14 at 15:55
  • \$\begingroup\$ thanks @CodesInChaos. In my early iterations, I used System for 3 things, then forgot to cleanup after eliminating the other 2. Code updated. \$\endgroup\$ – Richard II Aug 21 '14 at 16:01
  • 1
    \$\begingroup\$ Turing p into an int should save 6 chars. \$\endgroup\$ – CodesInChaos Aug 21 '14 at 16:20
  • \$\begingroup\$ yes @CodesInChaos, that thought also occurred to me over the weekend, and just hadn't gotten around to posting an update. \$\endgroup\$ – Richard II Aug 25 '14 at 15:36
  • \$\begingroup\$ reduced to 161 by changing from a command-line app to a simple method (after re-reading the rules) \$\endgroup\$ – Richard II Aug 28 '14 at 22:17
0
\$\begingroup\$

Japt -g, 8 bytes

õV ñ_k Ì

Try it


Explanation

             :Implicit input of integers U & V
õV           :Range [U,V]
   ñ_        :Sort by passing each through a function
     k       :  Prime factors
       Ì     :  Last element
             :Implicitly output the first element in that array
\$\endgroup\$
0
\$\begingroup\$

Julia, 58 bytes

using Primes
!r=[r;][indmin(max(factor(Set,n)...)for n=r)]

Takes a Range object of the form 5:9 as input, returns the smallest of the smoothest numbers in the range. (No TIO link, because TIO doesn't seem to have the Primes package.)

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 6 bytes

Input as a list of two items, outputs just one found integer in the [A,B] range (inclusive on both sides):

ŸΣfθ}н

Try it online or verify all test cases.

Explanation:

Ÿ          # Create a list in the inclusive range of the (implicit) input
           #  i.e. [9,15] → [9,10,11,12,13,14,15]
 Σ  }      # Sort it by:
  f        #  Get the prime factors
           #   i.e. 9 → [3]
           #   i.e. 10 → [2,5]
   θ       #  Pop and push the last item
           #   i.e. [3] → 3
           #   i.e. [2,5] → 5
           #  i.e. [9,10,11,12,13,14,15] → [9,12,10,15,14,11,13]
     н     # After sorting, pop and push the first item
           #  i.e. [9,12,10,15,14,11,13] → 9
           # (and output the result implicitly as result)

8 bytes alternative with same input-format, but outputs all found integers (as string) instead of one:

ŸDf€θWQÏ

Try it online or verify all test cases.

Explanation:

Ÿ          # Create a list in the inclusive range of the (implicit) input
           #  i.e. [9,15] → [9,10,11,12,13,14,15]
 D         # Duplicate this list
  f        # Get the prime factors of each
           #  i.e. [9,10,11,12,13,14,15] → [[3],[2,5],[11],[2,3],[13],[2,7],[3,5]]
   €θ      # Only leave the last value of each inner list
           #  i.e. [[3],[2,5],[11],[2,3],[13],[2,7],[3,5]] → [3,5,11,3,13,7,5]
     W     # Get the minimum of this list (without popping the list itself)
           #  i.e. [3,5,11,3,13,7,5] → 3
      Q    # Check for each value in the list if it is equal to this minimum
           #  i.e. [3,5,11,3,13,7,5] and 3 → [1,0,0,1,0,0,0]
       Ï   # Leave only the values of the duplicated list at the truthy indices
           #  i.e. [9,10,11,12,13,14,15] and [1,0,0,1,0,0,0] → ["9","12"]
           # (and output the result implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 44 bytes

Nθ≔…θNη≔¹ζW¬№η¹«≦⊕ζW⊙η¬﹪λζUMη⎇﹪λζλ÷λζ»I⁺θ⌕η¹

Try it online! Link is to verbose version of code. Takes input as a half-open range and returns the lowest smoothest number from that range. Works by trial division of all the numbers in the range until at least one has become completely factorised (in which case it is the smoothest). Explanation:

Nθ

Input the lower end of the range.

≔…θNη

Create an array covering the whole range.

≔¹ζ

Set the initial factor to 1.

W¬№η¹«

Repeat until there is at least one 1 in the array.

≦⊕ζ

Increment the factor.

W⊙η¬﹪λζ

Repeat while at least one element is divisible by the factor.

UMη⎇﹪λζλ÷λζ»

Divide all divisible elements by the factor.

I⁺θ⌕η¹

Look up the (first) index of the 1, add on the lower end of the range, and print the result as a string.

\$\endgroup\$
0
\$\begingroup\$

ECMAScript 2016 - 100 characters

m=>M=>(r=_=>M-m?[m,...r(++m)]:[])().sort((x,y)=>(s=(n,p=2)=>n>p?n%p?s(n,p+1):s(n/p,p):p)(x)-s(y))[0]

Definitely gets hurt by the lack of a built-in range.

This is a pretty standard anonymous function. It takes in a minimum (inclusive) and a maximum (exclusive), and then spits out the smallest smoothest number in that range.

\$\endgroup\$
0
\$\begingroup\$

MathGolf, 9 bytes

↨áæ─g¶╙0§

Try it online!

Explanation

Could be 1-2 bytes shorter with a "get prime factorization" operator.

↨           pop a, b, loop from a to b (inclusive)
 á          sort by comparator
  æ         start block of length 4
   ─        get divisors
    g       pop a, (b), pop operator from code, filter
     ¶      is_prime(n)
      ╙     maximum of two elements, max of list, maximum by filter
       0    push 0
        §   get from array
\$\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.