63
\$\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\$
5
  • \$\begingroup\$ Are ranges specified as (start,length) instead of (start,end) acceptable? \$\endgroup\$ Aug 21, 2014 at 16:26
  • 2
    \$\begingroup\$ @CodesInChaos Sure. It's covered under the "or whatever" clause. \$\endgroup\$
    – isaacg
    Aug 21, 2014 at 17:09
  • 4
    \$\begingroup\$ I don't see the point in penalizing non-ASCII answers. It would be simpler to just count bytes in all cases. \$\endgroup\$
    – Luna
    Aug 21, 2014 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, 2014 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, 2015 at 7:14

44 Answers 44

1
2
1
\$\begingroup\$

Java 8 - 422 454 chars

I'm learning Java 8, and wanted to give this a shot relative to Java (or even Java 8 streams).

Compared to other languages, this is brutal but an interesting exercise.

Golfed:

import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}

Ungolfed:

import java.util.stream.*;
import java.math.*;

class F {
    int v;
    int i;
    public int getV() { return v; }
    F (int i) { 
        this.i = i;
        v = IntStream.range(2,i+1)
                     .map( j -> ((i%j==0) && 
                           new BigInteger(""+j).isProbablePrime(1))?j:0)
                     .max()
                     .getAsInt();
    }
}

public class T {
    int s(int a, int b) {
        return IntStream.range(a,b+1)
                    .boxed()
                    .map(F::new)
                    .sorted(java.util.Comparator.comparingInt(F::getV))
                    .collect(java.util.stream.Collectors.toList())
                    .get(0).i;
    }
}

example run using:

public static void main(String[] s) {
    System.out.println(new T().s(157,249));
}

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

MATL (non-competitive), 20 bytes

This language was designed after the challenge

Range is inclusive at both ends. The numbers are taken as two separate inputs.

2$:t[]w"@YfX>v]4#X<)

Try it online!

Explanation

2$:          % implicitly input two numbers. Inclusive range
t            % duplicate                      
[]           % empty array
w            % swap elements in stack         
"            % for each                  
  @          %   push loop variable
  Yf         %   prime factors                  
  X>         %   maximum value
  v          %   vertical concatenation         
]            % end for each                         
4#X<         % arg min 
)            % index with this arg min into initial range of numbers
\$\endgroup\$
3
  • \$\begingroup\$ I guess today this would be 17 bytes &:[]y"@YfX>h]&X<) or perhaps 16 :[]y"@YfX>h]&X<). The & really was a great idea (and I'm guessing y wasn't available back then?). \$\endgroup\$
    – Sundar R
    Jul 10, 2018 at 13:53
  • \$\begingroup\$ And it looks like broadcast Yf with prefixed 1's would have been useful here too, but that's probably not enough to decide it's a good idea in general. :) \$\endgroup\$
    – Sundar R
    Jul 10, 2018 at 13:55
  • \$\begingroup\$ Yes, this was the very beginning, so no y or &. Credit to Suever for the very useful semantics of the latter (my initial idea was make it mean "one input more than default"). If we see more instances where Yf with adding ones would be useful, it may really be worth adding that feature. Problem is, there are about 34 answers that use Yf (according to this script), so it's hard to tell \$\endgroup\$
    – Luis Mendo
    Jul 10, 2018 at 15:13
1
\$\begingroup\$

Jelly, 7 bytes, score = 7÷7×8 = 8, language postdates challenge

rÆfṀ$ÐṂ

Try it online!

Takes the lower and upper range endpoints as two separate arguments. Outputs a list of all the smoothest numbers in the range. (This can be viewed as a function, in which case the output is a Jelly list, or as a full program, in which case the output happens to use the same list representation that JSON does.)

Explanation

Those times when your Jelly program is just a literal translation of the spec…

rÆfṀ$ÐṂ
r        Range from {first argument} to {second argument}
     ÐṂ  Return the elements which have the minimum
   Ṁ$      largest
 Æf          prime factor
\$\endgroup\$
1
\$\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\$
1
\$\begingroup\$

Factor + math.primes.factors, 37 bytes

[ [a,b) [ factors last ] infimum-by ]

Try it online!

Explanation:

This is a quotation (anonymous function) that takes two integers from the data stack as input and leaves one integer on the data stack as output. Assuming 2001 2014 is on top of the data stack when this quotation is called...

  • [a,b) Create a range object from two integers. The lower bound is included but the upper bound is excluded. Stack: T{ range f 2001 13 1 }
  • [ factors last ] Push a quotation to the data stack to be used later by the infimum-by word. Stack: T{ range f 2001 13 1 } [ factors last ]
  • infimum-by Apply a quotation to each element of a sequence, returning the element whose result is smallest. (Inside the quotation now...) Stack: 2001
  • factors Get the sorted list of prime factors given an integer. Stack: { 3 23 29 }
  • last Get the last element of a sequence. Stack: 29
  • Now infimum-by takes note of 29 and moves onto the next element in its input range...
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 5 bytes

ṡ‡ǐt∵

Try it Online!

ṡ     # Range from a to b
    ∵ # Minimum by...
 ‡--  # Next two as function
   t  # Last
  ǐ   # Prime factor
\$\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\$
5
  • \$\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\$ Aug 21, 2014 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, 2014 at 16:01
  • 1
    \$\begingroup\$ Turing p into an int should save 6 chars. \$\endgroup\$ Aug 21, 2014 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, 2014 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, 2014 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\$

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\$
0
\$\begingroup\$

Stax, 9 bytes

üwπ┼♦Σjô≤

Run and debug it

Thought this would be shorter.

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

Thunno 2 h, 4 bytes

IÞfG

Try it online!

Explanation

IÞfG  # Implicit input
I     # Range between the inputs
 Þ    # Sorted by the following:
  f   #  Prime factors of the number
   G  #  Take the maximum of this list
      # Implicit output of first item
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.