![]() |
![]() |
#1 |
Jun 2003
64516 Posts |
![]()
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 2006-03-20 at 06:24 |
![]() |
![]() |
![]() |
#2 |
Aug 2002
Buenos Aires, Argentina
3·499 Posts |
![]()
126 is not a special smooth number since:
126 = 2 * 32 * 7 log2 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 2006-03-20 at 11:51 |
![]() |
![]() |
![]() |
#3 | |
"Bob Silverman"
Nov 2003
North of Boston
1D5416 Posts |
![]() Quote:
I can prove it, but the proof is not elementary. It isn't complicated, but requires sieve methods and the Brun-Titschmarsh 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^2-1, x^2 [BTW, look at your examples] Last fiddled with by ewmayer on 2006-03-20 at 17:09 Reason: For th sake of brevity, quoted only the relevant part of citrix's post |
|
![]() |
![]() |
![]() |
#4 |
Aug 2002
Buenos Aires, Argentina
27318 Posts |
![]()
I wrote the following ultra non-optimized 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", count-1, count); } } } It appears that the pairs are very scarce. |
![]() |
![]() |
![]() |
#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 2006-03-20 at 17:20 |
|
![]() |
![]() |
![]() |
#6 | |
Jun 2003
160510 Posts |
![]() Quote:
Dr. Silverman, I don't think x^2 and x^2-1 is a hint, it makes things more challenging. Because, if both of them are smooth then x-1,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! |
|
![]() |
![]() |
![]() |
#7 | |
∂2ω=0
Sep 2002
República de California
5·2,351 Posts |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#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 p-smooth numbers in the necessary interval so ceil(log2(x^2)) <= p and ceil(log2(x^2)) > previous prime OR sqrt(2)*2^((previousp-1)/2) < x < sqrt(2)*2^((p-1)/2) and then test the neighbors for smoothness. If you use x^2, you will be doing far, far fewer calculations. |
![]() |
![]() |
![]() |
#9 |
Aug 2002
Buenos Aires, Argentina
101110110012 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)(count-1) * (__int64)(count-1); printf("%I64d - %I64d\n", c64-1, 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 264. Thus if there is another pair less than 264, the greatest member cannot be a perfect square. |
![]() |
![]() |
![]() |
#10 |
"Robert Gerbicz"
Oct 2005
Hungary
64F16 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. |
![]() |
![]() |
![]() |
#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 1012.
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 1012. |
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Not smooth enough numbers | Sam Kennedy | Factoring | 5 | 2012-11-10 07:54 |
Distribution of Smooth Numbers | flouran | Math | 12 | 2009-12-25 16:41 |
Smooth and rough numbers | CRGreathouse | Math | 3 | 2009-05-25 05:26 |
Finding smooth numbers | Citrix | Math | 9 | 2005-12-31 11:07 |
Smooth Numbers | Yamato | Math | 1 | 2005-12-11 11:09 |