18
\$\begingroup\$

In arithmetic, an n-smooth number, where n is a given prime number, is mathematically defined as a positive integer that has no prime factors greater than n. For example, 42 is 7-smooth because all its prime factors are less than or equal to 7, but 44 is not 7-smooth because it also has 11 as a prime factor.

Define a pretty smooth number as a number with no prime factors greater than its own square root. Thus, the list of pretty smooth numbers can be formulated as follows:

  • (EDITED!) 1 is a pretty smooth number, due to its complete lack of any prime factors. (Note that in the original version of this question, 1 was erroneously excluded from the list, so if you exclude it from your outputs you won't be marked wrong.)
  • Between 4 (= 22) and 8, the pretty smooth numbers are 2-smooth, meaning they have 2 as their only prime factor.
  • Between 9 (= 32) and 24, the pretty smooth numbers are 3-smooth, and can have 2s and 3s in their prime factorizations.
  • Between 25 (= 52) and 48, the pretty smooth numbers are 5-smooth, and can have 2s, 3s, and 5s in their prime factorizations.
  • And so on, upgrading the criteria every time the square of the next prime number is reached.

The list of pretty smooth numbers is fixed, and begins as follows: 1, 4, 8, 9, 12, 16, 18, 24, 25, ...

Your challenge is to write code that will output all pretty smooth numbers up to and including 10,000 (= 1002). There must be at least one separator (it doesn't matter what kind -- space, comma, newline, anything) between each number in the list and the next, but it is completely irrelevant what character is used.

As per usual, lowest byte count wins -- obviously, simply outputting the list isn't going to be too beneficial to you here. Good luck!

\$\endgroup\$
  • 9
    \$\begingroup\$ Why is 1 not pretty smooth? \$\endgroup\$ – Dennis Aug 15 '16 at 2:48
  • \$\begingroup\$ Can we output the list in reverse order? \$\endgroup\$ – Leaky Nun Aug 15 '16 at 3:20
  • 5
    \$\begingroup\$ OEIS A048098 (includes extra 1) \$\endgroup\$ – Leaky Nun Aug 15 '16 at 5:20
  • 1
    \$\begingroup\$ @Mego "There are no pretty smooth numbers less than 4." is pretty clear. Not necessarily obvious, but definitely clear. \$\endgroup\$ – viraptor Aug 15 '16 at 10:40
  • 1
    \$\begingroup\$ @viraptor It is voted as not clear not because it wasn't stated that 1 is not smooth, but because your definition and your exclusion statement contradict each other. \$\endgroup\$ – Leaky Nun Aug 15 '16 at 11:45

14 Answers 14

1
\$\begingroup\$

Actually, 11 bytes

4╤R`;yM²≤`░

Try it online!

Does not include 1.

Explanation:

4╤R`;yM²≤`░
4╤R          range(10**4)
   `;yM²≤`░  filter: take values where
    ;yM²       the square of the largest prime factor
        ≤      is less than or equal to the value
\$\endgroup\$
7
\$\begingroup\$

Jelly, 12 bytes

Æf>½S
³²ḊÇÐḟ

Try it online!

How it works

³²ḊÇÐḟ  Main link. No arguments.

³       Yield 100.
 ²      Square it to yield 10,000.
  Ḋ     Dequeue; yield [2, ..., 10,000].
   ÇÐḟ  Filter-false; keep elements for which the helper link returns 0.

Æf>½S   Helper link. Argument: n

Æf      Compute the prime factorization of n.
  >½    Compare the prime factors with the square root of n.
    S   Sum; add the resulting Booleans.
\$\endgroup\$
7
\$\begingroup\$

Brachylog, 21 19 bytes

1 byte thanks to Fatalize, for inspiration of another 1 byte.

100^:4reP$ph^<=P@w\

Try it online!

Takes about 6 seconds here.

100^:4reP$ph^<=P@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P$ph^<=P         P, prime factorized (from biggest to smallest),
                         take the first element, squared, is less than
                         or equal to P
               P@w       Write P with a newline,
                  \      Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.

Previous 21-byte solution

100^:4reP'($pe^>P)@w\

Try it online!

Takes about 6 seconds here.

100^:4reP'($pe^>P)@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P'(      )       The following about P cannot be proved:
           $pe               one of its prime factor
              ^              squared
               >P            is greater than P
                  @w     Write P with a newline,
                    \    Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.
\$\endgroup\$
  • \$\begingroup\$ 100^:4reP$pot^<=P@w\ is one byte shorter, though less elegant. \$\endgroup\$ – Fatalize Aug 16 '16 at 7:10
  • \$\begingroup\$ @Fatalize Thanks, I golfed off another byte \$\endgroup\$ – Leaky Nun Aug 16 '16 at 7:21
4
\$\begingroup\$

Haskell, 53 bytes

r=[1..10^4]
[n|n<-r,product[x|x<-r,x*x<=n]^n`mod`n<1]

I don't have time to golf this now, but I want to illustrate a method for testing if n is pretty smooth: Multiply the numbers from 1 to sqrt(n) (i.e. compute a factorial), raise the product to a high power, and check if the result is a multiple of n.

Change to r=[2..10^4] if 1 should not be output.

\$\endgroup\$
  • \$\begingroup\$ Not that it's any golfier, but I'm pretty sure the cube suffices (8 requires it). \$\endgroup\$ – Neil Aug 15 '16 at 8:38
2
\$\begingroup\$

Pyth, 16 15 bytes

1 byte thanks to Jakube.

tf!f>*YYTPTS^T4

Try it online!

tf!f>*YYTPTS^T4
             T   10
            ^T4  10000
           S^T4  [1,2,3,...,10000]
 f               filter for elements as T for
                 which the following is truthy: 
         PT          prime factorization of T
   f                 filter for factor as Y:
     *YY                 Y*Y
    >   T                greater than T ?
  !                  logical negation
t                remove the first one (1)
\$\endgroup\$
  • \$\begingroup\$ Surely Pyth has a square function? So you can replace *dd with that function? \$\endgroup\$ – Conor O'Brien Aug 15 '16 at 4:19
  • \$\begingroup\$ @ConorO'Brien Nope, Pyth has not a square function. \$\endgroup\$ – Leaky Nun Aug 15 '16 at 4:21
  • \$\begingroup\$ that seems like kind of an oversight \$\endgroup\$ – Conor O'Brien Aug 15 '16 at 4:23
2
\$\begingroup\$

05AB1E, 16 14 13 bytes

4°L¦vyf¤yt›_—

Explanation

4°L¦v             # for each y in range 2..10000
      yf¤         # largest prime factor of y
         yt       # square root of y
           ›_     # less than or equal
             —    # if true then print y with newline

Try it online

\$\endgroup\$
  • \$\begingroup\$ is short for 10000. \$\endgroup\$ – Adnan Aug 15 '16 at 8:47
  • \$\begingroup\$ @Adnan Thanks! Forgot about that one. \$\endgroup\$ – Emigna Aug 15 '16 at 8:50
2
\$\begingroup\$

Matlab, 58 57 56 52 48 bytes

for k=1:1e4
if factor(k).^2<=k
disp‌​(k)
end
end

For each number it checks if all factors squared are not larger than the number itself. If yes, displays that number.

Thanks to @Luis Mendo for golfing this approach


Another approach (50 bytes):

n=1:10^4;for k=n
z(k)=max(factor(k))^2>k;end
n(~z)

For each number computes whether its maximum prime factor squared is less than the number itself. Then uses it for indexing.

\$\endgroup\$
  • 1
    \$\begingroup\$ Your previous approach can be made shorter: for k=4:1e4,if factor(k).^2<=k,disp(k);end;end \$\endgroup\$ – Luis Mendo Aug 15 '16 at 14:56
1
\$\begingroup\$

SQF, 252 227 220

Standard script format:

#define Q(A,B) for #A from 2 to B do{
Q(i,10000)if([i]call{params["j"];u=sqrt j;a=true;Q(k,u)a=a and((j%k!=0)or(j/k<u)or!([j/k]call{params["x"];q=true;Q(z,sqrt x)q=q and(x%z!=0)};q}))};a})then{systemChat format["%1",i]}}

Include the pre-processor in the compilation chain when calling eg:

  • execVM "FILENAME.sqf"
  • call compile preprocessFile "FILENAME.sqf"

This writes to the System Chat log, which is the closest thing SQF has to stdout

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

C, 113 bytes

#include<stdio.h>
main(a){for(;++a<10001;){int n=2,c=a;for(;n*n<=a;n++)while(c%n<1)c/=n;if(c<2)printf("%d ",a);}}

Ideone it!

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

Pyke, 13 12 11 bytes

T4^S#DP#X<!

Try it here!

(Link only goes up to 10^3 because 10^4 times out)

T4^S        -  one_range(10^4)
    #DP#X<! - filter_true(V, ^): (as i)
      P     -   factors(i)
       #X<! -  filter_true(V, ^):
        X   -   ^ ** 2
         <! -    not (i < ^)
\$\endgroup\$
1
\$\begingroup\$

J, 20 bytes

(#~{:@q:<:%:)2+i.1e4

Result:

   (#~{:@q:<:%:)2+i.1e4
4 8 9 12 16 18 24 25 27 30 32 36 40 45 48 49 50 54 56 60 63 64 70 72 75 80...

Try it online here.

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

Python 2, 90 bytes

for i in range(4,10001):
 n=2;j=i
 while n*n<=j:
  while i%n<1:i/=n
  n+=1
 if i<2:print j

Ideone it!

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

R, 97 bytes

b=F;for(j in 1:1e4){for(i in which(!j%%1:j)[-1])if(which(!i%%1:i)[2]==i)b=i<=j^0.5;if(b)print(j)}

ungolfed

b <- F                               #Initializes
for (j in 1:1e4){                    #Loop across integers 1..10^4
    a <- which(!j%%1:j)[-1]          #Finds all factors
    for (i in a)                     #Loop across factors
         b <- which(!i%%1:i)[2]==i   #Tests primeness
         if(b) c <- i<=j^0.5         #If prime, tests smoothness
    if(c) print(j)                   #If biggest prime factor gives smooth
}                                    #result, Prints the number.
\$\endgroup\$
0
\$\begingroup\$

Pyth, 12 bytes

g#^ePT2tS^T4

Does not include 1.

\$\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.