Special Smooth numbers

[Citrix]

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

[alpertron]

126 is not a special smooth number since:

126 = 2 * 3² * 7

log₂ 126 = 6.977...

[Edit] Sorry I didn't read the "rounded off to larger number" part. Forget what I wrote above.

[R.D. Silverman]

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]

[alpertron]

I wrote the following ultra non-optimized program in C language:

#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 2³² it found this new pair: 1611308699 - 1611308700.

It appears that the pairs are very scarce.

[ewmayer]

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

[Citrix]

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!

[ewmayer]

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.

[grandpascorpion]

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.

[alpertron]

... but you don't get any new result.

I changed the program to:

#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 2⁶⁴. Thus if there is another pair less than 2⁶⁴, the greatest member cannot be a perfect square.

[R. Gerbicz]

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.

[alpertron]

By using sieving and assembler language I think it should not be difficult to compute up to the bound 10¹².

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¹².