mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2006-03-20, 06:24   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

30508 Posts
Default 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
Citrix is offline   Reply With Quote
Old 2006-03-20, 11:48   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×223 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2006-03-20, 12:00   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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
R.D. Silverman is offline   Reply With Quote
Old 2006-03-20, 13:35   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×223 Posts
Default

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);
    }
  }
}
After running up to 232 it found this new pair: 1611308699 - 1611308700.

It appears that the pairs are very scarce.
alpertron is offline   Reply With Quote
Old 2006-03-20, 17:16   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

1157110 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2006-03-20, 19:07   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

23×197 Posts
Default

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!
Citrix is offline   Reply With Quote
Old 2006-03-20, 19:35   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3·7·19·29 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-03-20, 20:02   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2006-03-20, 21:16   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

133810 Posts
Default

... 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);
    }
  }
}
and its output is:

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.
alpertron is offline   Reply With Quote
Old 2006-03-20, 21:26   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101100011002 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2006-03-20, 21:34   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×223 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
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

All times are UTC. The time now is 22:13.

Sat Dec 5 22:13:08 UTC 2020 up 2 days, 18:24, 0 users, load averages: 1.26, 1.46, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.