mersenneforum.org Special Smooth numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2006-03-20, 06:24 #1 Citrix     Jun 2003 1,579 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 2006-03-20 at 06:24
 2006-03-20, 11:48 #2 alpertron     Aug 2002 Buenos Aires, Argentina 54416 Posts 126 is not a special smooth number since: 126 = 2 * 32 * 7 log2 126 = 6.977...  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
2006-03-20, 12:00   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Citrix 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?
There should be infinitely many. I have a strong heuristic, and *think*
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

 2006-03-20, 13:35 #4 alpertron     Aug 2002 Buenos Aires, Argentina 134810 Posts I wrote the following ultra non-optimized program in C language: Code: #include #include #include #include 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
2006-03-20, 17:16   #5
ewmayer
2ω=0

Sep 2002
República de California

2·5,813 Posts

Quote:
 Originally Posted by Citrix The question is that are there infinite pairs of special smooth numbers differing by 1?
Another way of looking at this question, which might perhaps be useful: if one relaxes the smoothness bound, then in the upper limit of N-smooth we know there are infinitely many such pairs, since all numbers, prime or composite, are N-smooth. One should be able to sharpen this upper bound considerably, e.g. by using the fact that the composites are asymptotically dense among the primes. At the other extreme, once we get down to the minimum possible limit of 2-smoothness we know there are no such pairs since only powers of 2 are 2-smooth. Your question would seem to be a special case of the more general one of precisely where this "phase transition" (to borrow a term from physics) occurs.

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

2006-03-20, 19:07   #6
Citrix

Jun 2003

62B16 Posts

Quote:
 Originally Posted by ewmayer Another way of looking at this question, which might perhaps be useful: if one relaxes the smoothness bound, then in the upper limit of N-smooth we know there are infinitely many such pairs, since all numbers, prime or composite, are N-smooth. One should be able to sharpen this upper bound considerably, e.g. by using the fact that the composites are asymptotically dense among the primes. At the other extreme, once we get down to the minimum possible limit of 2-smoothness we know there are no such pairs since only powers of 2 are 2-smooth. Your question would seem to be a special case of the more general one of precisely where this "phase transition" (to borrow a term from physics) occurs. Bear in mind that this is way out of my area of expertise, and I've just started on my first cup of coffee...
I kind of agree with you. But if you stick with say 2 and 3 smooth numbers only, you run out of numbers that differ by 1 at 9. So the bound must be defined in terms of the number n such as log(n). Now the question is what must the lowest function be so that there are infinite solutions to the question?

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!

2006-03-20, 19:35   #7
ewmayer
2ω=0

Sep 2002
República de California

1162610 Posts

Quote:
 Originally Posted by Citrix Iif you stick with say 2 and 3 smooth numbers only, you run out of numbers that differ by 1 at 9. So the bound must be defined in terms of the number n such as log(n).
Not necessarily - e.g. if you ask how many prime pairs there are that differ by one you have only (2,3), but if you allow the difference to be 2, things suddenly get much more interesting. So even though I suspect you are right, that's not the same as a proof.

 2006-03-20, 20:02 #8 grandpascorpion     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.
 2006-03-20, 21:16 #9 alpertron     Aug 2002 Buenos Aires, Argentina 25048 Posts ... but you don't get any new result. I changed the program to: Code: #include #include #include #include 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
 2006-03-20, 21:26 #10 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 1,459 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.
 2006-03-20, 21:34 #11 alpertron     Aug 2002 Buenos Aires, Argentina 25048 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 flouran Math 12 2009-12-25 16:41 CRGreathouse Math 3 2009-05-25 05:26 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 19:39.

Tue Apr 20 19:39:27 UTC 2021 up 12 days, 14:20, 1 user, load averages: 3.38, 3.09, 3.13