20060320, 06:24  #1 
Jun 2003
645_{16} Posts 
Special Smooth numbers
Let a number n be a special smooth number if it is log2(n) smooth.(Rounded off to larger number)
Then for example 125 is a special smooth number since it is 5 smooth which is less than log2(125)~7 The question is that are there infinite pairs of special smooth numbers differing by 1? Also is there a fast method to generate these special smooth numbers and test if the pair is also smooth? I have checked this to 125M and found the following, are there any more? 1 2 3 4 8 9 24 25 80 81 125 126 224 225 2400 2401 3024 3025 4224 4225 4374 4375 6655 6656 9800 9801 10647 10648 123200 123201 194480 194481 336140 336141 601425 601426 633555 633556 709631 709632 5142500 5142501 5909760 5909761 11859210 11859211 Thanks, Citrix Last fiddled with by Citrix on 20060320 at 06:24 
20060320, 11:48  #2 
Aug 2002
Buenos Aires, Argentina
3·499 Posts 
126 is not a special smooth number since:
126 = 2 * 3^{2} * 7 log_{2} 126 = 6.977... [Edit] Sorry I didn't read the "rounded off to larger number" part. Forget what I wrote above. Last fiddled with by alpertron on 20060320 at 11:51 
20060320, 12:00  #3  
"Bob Silverman"
Nov 2003
North of Boston
1D54_{16} Posts 
Quote:
I can prove it, but the proof is not elementary. It isn't complicated, but requires sieve methods and the BrunTitschmarsh theorem. I will look into it when I can find the time. Hint: Suppose x is odd and smooth (or *nearly* smooth). Consider the pair x^21, x^2 [BTW, look at your examples] Last fiddled with by ewmayer on 20060320 at 17:09 Reason: For th sake of brevity, quoted only the relevant part of citrix's post 

20060320, 13:35  #4 
Aug 2002
Buenos Aires, Argentina
2731_{8} Posts 
I wrote the following ultra nonoptimized program in C language:
Code:
#include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> int primes[] = {2,3,5,7,11,13,17,19,23,29,31}; unsigned int bounds[] = {1<<1,1<<2,1<<4,1<<6,1<<10,1<<12,1<<16,1<<18, 1<<22,1<<28,1<<30}; int oldsmooth = 0; int newsmooth = 0; int isSmooth(unsigned int count) { int i,j; unsigned int quotient, prime; for (i=0;i<11;i++) { if (bounds[i] >= count) { break; } } for (j=0; j<i; j++) { prime = primes[j]; while (1) { quotient = count / prime; if (quotient*prime != count) { break; } count = quotient; } } return count == 1; } int main(int argc, char *argv[]) { unsigned int count; oldsmooth = 0; for (count = 2; count < 0xFFFFFFFEUL; count ++) { oldsmooth = newsmooth; newsmooth = isSmooth(count); if (oldsmooth && newsmooth) { printf("%u  %u\n", count1, count); } } } It appears that the pairs are very scarce. 
20060320, 17:16  #5  
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 
Quote:
Bear in mind that this is way out of my area of expertise, and I've just started on my first cup of coffee... Last fiddled with by ewmayer on 20060320 at 17:20 

20060320, 19:07  #6  
Jun 2003
1605_{10} Posts 
Quote:
Dr. Silverman, I don't think x^2 and x^21 is a hint, it makes things more challenging. Because, if both of them are smooth then x1,x,x+1 are also smooth, which is finding 3 smooth numbers, so I think this will be harder than finding 2 smooth numbers. If you still think they are infinite and easy to find, please explain your work. Thanks! 

20060320, 19:35  #7  
∂^{2}ω=0
Sep 2002
República de California
5·2,351 Posts 
Quote:


20060320, 20:02  #8 
Jan 2005
Transdniestr
503 Posts 
Citrix,
I agree with Dr. Silverman. If you can construct the smaller three smaller smooth numbers and then voila, have one type of solution. Granted it's not exhaustive but you could easily write a brute force search to find all the odd psmooth numbers in the necessary interval so ceil(log2(x^2)) <= p and ceil(log2(x^2)) > previous prime OR sqrt(2)*2^((previousp1)/2) < x < sqrt(2)*2^((p1)/2) and then test the neighbors for smoothness. If you use x^2, you will be doing far, far fewer calculations. 
20060320, 21:16  #9 
Aug 2002
Buenos Aires, Argentina
10111011001_{2} Posts 
... but you don't get any new result.
I changed the program to: Code:
#include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; unsigned int bounds[] = {1<<(2/2),1<<(3/2),1<<(5/2),1<<(7/2), 1<<(11/2),1<<(13/2),1<<(17/2),1<<(19/2), 1<<(23/2),1<<(29/2),1<<(31/2),1<<(37/2), 1<<(41/2),1<<(43/2),1<<(47/2),1<<(53/2), 1<<(59/2),1<<(61/2)}; int veryoldsmooth = 0; int oldsmooth = 0; int newsmooth = 0; int isSmooth(unsigned int count) { int i,j; unsigned int quotient, prime; for (i=0;i<11;i++) { if (bounds[i] >= count) { break; } } for (j=0; j<i; j++) { prime = primes[j]; while (1) { quotient = count / prime; if (quotient*prime != count) { break; } count = quotient; } } return count == 1; } int main(int argc, char *argv[]) { unsigned int count; __int64 c64; veryoldsmooth = 0; oldsmooth = 0; for (count = 2; count < 0xFFFFFFFEUL; count ++) { veryoldsmooth = oldsmooth; oldsmooth = newsmooth; newsmooth = isSmooth(count); if (veryoldsmooth && oldsmooth && newsmooth) { c64 = (__int64)(count1) * (__int64)(count1); printf("%I64d  %I64d\n", c641, c64); } } } 15  16 24  25 80  81 224  225 2400  2401 3024  3025 4095  4096 4224  4225 9800  9801 123200  123201 194480  194481 5909760  5909761 The bounds are not computed correctly (they are set very high), so the program prints some additional (but incorrect) results. There are no results greater than the ones known, even when the program was able to reach 2^{64}. Thus if there is another pair less than 2^{64}, the greatest member cannot be a perfect square. 
20060320, 21:26  #10 
"Robert Gerbicz"
Oct 2005
Hungary
64F_{16} Posts 
There is a similar sequence in the Neil Sloane database: http://www.research.att.com/~njas/sequences/A002072
Seeing this it is very very unprobable that there is another solution. 
20060320, 21:34  #11 
Aug 2002
Buenos Aires, Argentina
3×499 Posts 
By using sieving and assembler language I think it should not be difficult to compute up to the bound 10^{12}.
Up to now the list is: 8 9 24 25 80 81 125 126 224 225 2400 2401 3024 3025 4224 4225 4374 4375 6655 6656 9800 9801 10647 10648 123200 123201 194480 194481 336140 336141 601425 601426 633555 633556 709631 709632 5142500 5142501 5909760 5909761 11859210 11859211 1611308699 1611308700 Maybe there is one missing pair below 10^{12}. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 
Smooth and rough numbers  CRGreathouse  Math  3  20090525 05:26 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 
Smooth Numbers  Yamato  Math  1  20051211 11:09 