Pretty Smooth Moves

Question 1

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 (= 2²) and 8, the pretty smooth numbers are 2-smooth, meaning they have 2 as their only prime factor.
Between 9 (= 3²) and 24, the pretty smooth numbers are 3-smooth, and can have 2s and 3s in their prime factorizations.
Between 25 (= 5²) 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 (= 100²). 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!

Question 2

Why is 1 not pretty smooth?

Question 3

OEIS A048098 (includes extra 1)

Question 4

@Mego "There are no pretty smooth numbers less than 4." is pretty clear. Not necessarily obvious, but definitely clear.

Question 5

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

Question 6

Sorry! This was a complete mistake, and "1" should indeed have been listed as pretty smooth. If anyone outputs the list according to the original criteria (i.e., excluding 1 from the list), they won't be marked wrong, but it would seem to me that including the 1 will cut down on answer length.

Question 7

Jelly, 12 bytes

Æf>1⁄2S
32ḊÇÐḟ

Try it online!

How it works

32ḊÇÐḟ Main link. No arguments.
3 Yield 100.
 2 Square it to yield 10,000.
 Ḋ Dequeue; yield [2, ..., 10,000].
 ÇÐḟ Filter-false; keep elements for which the helper link returns 0.
Æf>1⁄2S Helper link. Argument: n
Æf Compute the prime factorization of n.
 >1⁄2 Compare the prime factors with the square root of n.
 S Sum; add the resulting Booleans.

Question 8

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.

Question 9

100^:4reP$pot^<=P@w\ is one byte shorter, though less elegant.

Question 10

@Fatalize Thanks, I golfed off another byte

Question 11

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.

Question 12

Not that it's any golfier, but I'm pretty sure the cube suffices (8 requires it).

Question 13

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)

Question 14

Surely Pyth has a square function? So you can replace *dd with that function?

Question 15

@ConorO'Brien Nope, Pyth has not a square function.

Question 16

that seems like kind of an oversight

Question 17

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

Question 18

4° is short for 10000.

Question 19

@Adnan Thanks! Forgot about that one.

Question 20

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.

Question 21

Your previous approach can be made shorter: for k=4:1e4,if factor(k).^2<=k,disp(k);end;end

Question 22

Actually, 11 bytes

4╤R`;yM2≤`░

Try it online!

Does not include 1.

Explanation:

4╤R`;yM2≤`░
4╤R range(10**4)
 `;yM2≤`░ filter: take values where
 ;yM2 the square of the largest prime factor
 ≤ is less than or equal to the value

Question 23

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

Question 24

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!

Question 25

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

Question 26

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.

Question 27

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!

Question 28

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.

Question 29

Pyth, 12 bytes

g#^ePT2tS^T4

Does not include 1.

Dennis 212k41 gold badges380 silver badges830 bronze badges · Answer 1 · 2016-08-15 02:50:11Z

Jelly, 12 bytes

Æf>1⁄2S
32ḊÇÐḟ

Try it online!

How it works

32ḊÇÐḟ Main link. No arguments.
3 Yield 100.
 2 Square it to yield 10,000.
 Ḋ Dequeue; yield [2, ..., 10,000].
 ÇÐḟ Filter-false; keep elements for which the helper link returns 0.
Æf>1⁄2S Helper link. Argument: n
Æf Compute the prime factorization of n.
 >1⁄2 Compare the prime factors with the square root of n.
 S Sum; add the resulting Booleans.

Leaky Nun 50.6k6 gold badges115 silver badges291 bronze badges · Answer 2 · 2016-08-15 03:18:29Z

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.

100^:4reP$pot^<=P@w\ is one byte shorter, though less elegant.

xnor 150k26 gold badges287 silver badges676 bronze badges · Answer 3 · 2016-08-15 07:53:54Z

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.

Not that it's any golfier, but I'm pretty sure the cube suffices (8 requires it).

Leaky Nun 50.6k6 gold badges115 silver badges291 bronze badges · Answer 4 · 2016-08-15 03:58:43Z

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)

Share

Improve this answer

edited Aug 15, 2016 at 5:10

answered Aug 15, 2016 at 3:58

Leaky Nun's user avatar

Leaky Nun

50.6k6 gold badges115 silver badges291 bronze badges

\$\endgroup\$

3

\$\begingroup\$ Surely Pyth has a square function? So you can replace *dd with that function? \$\endgroup\$

Conor O'Brien
– Conor O'Brien

2016年08月15日 04:19:52 +00:00
Commented Aug 15, 2016 at 4:19
\$\begingroup\$ @ConorO'Brien Nope, Pyth has not a square function. \$\endgroup\$

Leaky Nun
– Leaky Nun

2016年08月15日 04:21:15 +00:00
Commented Aug 15, 2016 at 4:21
\$\begingroup\$ that seems like kind of an oversight \$\endgroup\$

Conor O'Brien
– Conor O'Brien

2016年08月15日 04:23:07 +00:00
Commented Aug 15, 2016 at 4:23

Add a comment |

Emigna 53.2k5 gold badges44 silver badges164 bronze badges · Answer 5 · 2016-08-15 08:16:21Z

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

Share

Improve this answer

edited Jun 17, 2020 at 9:04

Community's user avatar

Community Bot

1

answered Aug 15, 2016 at 8:16

Emigna's user avatar

Emigna

53.2k5 gold badges44 silver badges164 bronze badges

\$\endgroup\$

2

\$\begingroup\$ 4° is short for 10000. \$\endgroup\$

Adnan
– Adnan

2016年08月15日 08:47:48 +00:00
Commented Aug 15, 2016 at 8:47
\$\begingroup\$ @Adnan Thanks! Forgot about that one. \$\endgroup\$

Emigna
– Emigna

2016年08月15日 08:50:27 +00:00
Commented Aug 15, 2016 at 8:50

Add a comment |

pajonk 19.4k5 gold badges29 silver badges78 bronze badges · Answer 6 · 2016-08-15 10:49:29Z

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.

Your previous approach can be made shorter: for k=4:1e4,if factor(k).^2<=k,disp(k);end;end

user45941 · Answer 7 · 2016-08-15 19:29:56Z

Actually, 11 bytes

4╤R`;yM2≤`░

Try it online!

Does not include 1.

Explanation:

4╤R`;yM2≤`░
4╤R range(10**4)
 `;yM2≤`░ filter: take values where
 ;yM2 the square of the largest prime factor
 ≤ is less than or equal to the value

Οurous 8,1571 gold badge17 silver badges38 bronze badges · Answer 8 · 2016-08-15 03:22:47Z

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

Leaky Nun 50.6k6 gold badges115 silver badges291 bronze badges · Answer 9 · 2016-08-15 04:58:50Z

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!

Share

Improve this answer

edited Aug 15, 2016 at 5:06

answered Aug 15, 2016 at 4:58

Leaky Nun's user avatar

Leaky Nun

50.6k6 gold badges115 silver badges291 bronze badges

\$\endgroup\$

Add a comment |

Blue 28.8k8 gold badges53 silver badges101 bronze badges · Answer 10 · 2016-08-15 07:59:58Z

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

randomra 20.9k4 gold badges48 silver badges113 bronze badges · Answer 11 · 2016-08-15 09:44:30Z

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.

Leaky Nun 50.6k6 gold badges115 silver badges291 bronze badges · Answer 12 · 2016-08-15 04:35:25Z

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!

Share

Improve this answer

answered Aug 15, 2016 at 4:35

Leaky Nun's user avatar

Leaky Nun

50.6k6 gold badges115 silver badges291 bronze badges

\$\endgroup\$

Add a comment |

user5957401 7693 silver badges5 bronze badges · Answer 13 · 2016-08-15 15:01:32Z

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.

izzyg 42.3k5 gold badges79 silver badges216 bronze badges · Answer 14 · 2016-08-15 16:57:37Z

0

\$\begingroup\$

Pyth, 12 bytes

g#^ePT2tS^T4

Does not include 1.

Share

Improve this answer

answered Aug 15, 2016 at 16:57

izzyg's user avatar

izzyg

42.3k5 gold badges79 silver badges216 bronze badges

\$\endgroup\$

Add a comment |

Stack Exchange Network

Pretty Smooth Moves

14 Answers 14

Jelly, 12 bytes

How it works

Brachylog, (削除) 21 (削除ここまで) 19 bytes

Previous 21-byte solution

Haskell, 53 bytes

Pyth, (削除) 16 (削除ここまで) 15 bytes

05AB1E, (削除) 16 (削除ここまで) (削除) 14 (削除ここまで) 13 bytes

Matlab, (削除) 58 (削除ここまで) (削除) 57 (削除ここまで) (削除) 56 (削除ここまで) (削除) 52 (削除ここまで) 48 bytes

Actually, 11 bytes

SQF, (削除) 252 (削除ここまで) (削除) 227 (削除ここまで) 220

C, 113 bytes

Pyke, (削除) 13 (削除ここまで) (削除) 12 (削除ここまで) 11 bytes

J, 20 bytes

Python 2, 90 bytes

R, 97 bytes

Pyth, 12 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Hot Network Questions

Pretty Smooth Moves

14 Answers 14

Jelly, 12 bytes

How it works

Brachylog, (削除) 21 (削除ここまで) 19 bytes

Previous 21-byte solution

Haskell, 53 bytes

Pyth, (削除) 16 (削除ここまで) 15 bytes

05AB1E, (削除) 16 (削除ここまで) (削除) 14 (削除ここまで) 13 bytes

Matlab, (削除) 58 (削除ここまで) (削除) 57 (削除ここまで) (削除) 56 (削除ここまで) (削除) 52 (削除ここまで) 48 bytes

Actually, 11 bytes

SQF, (削除) 252 (削除ここまで) (削除) 227 (削除ここまで) 220

C, 113 bytes

Pyke, (削除) 13 (削除ここまで) (削除) 12 (削除ここまで) 11 bytes

J, 20 bytes

Python 2, 90 bytes

R, 97 bytes

Pyth, 12 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions