Loading ...
Sorry, an error occurred while loading the content.

Primes and Three Smooth numbers

Expand Messages
  • marku606
    Three smooth numbers are numbers that have at most factors of two and three. The three smooth numbers up to a thousand are
    Message 1 of 1 , Oct 26, 2009
    • 0 Attachment
      "Three smooth" numbers are numbers that have at most factors of two and three. The three smooth numbers up to a thousand are

      1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192,216,243,256,288,324,384,432,486,512,576,648,729,768,864,972.

      Question: Can every number > 2 be written as a three smooth number multiplied by the sum of a prime and a three smooth number?

      Examples:

      3 = 1*(2+1)
      4 = 1*(2+2)
      5 = 1*(2+3)
      6 = 1*(3+3) = 2*(2+1)
      7 = 1*(3+4) = 1*(5+1)
      8 = 1*(2+6) = 2*(2+2)
      9 = 1*(3+6) = 1*(5+4) = 1*(7+2) = 3*(2+1)
      10 = 1*(2+8) = 1*(7+3) = 2*(2+3)
      11 = 1*(2+9) = 1*(3+8) = 1*(5+6) = 1*(7+4)

      To test the idea, it is enough to check out numbers that have no factors of 2 or 3. In other words we check out numbers of the form 6n +/- 1.

      My program first generated and sorted (in a fraction of a second) all the three smooth numbers up to a billion. (There are only a little over 300 such numbers.) Then, as the numbers of the form 6n +/- 1 incremented up to a billion, the program noted the largest three smooth number up to that number. It then subtracts progressively smaller three smooth numbers from the original number until it finally obtains a prime. The program noted how many three smooth numbers it went through in order to obtain the prime. It outputted only those results where an increasing number of three smooth numbers were required to be processed before a prime solution was reached.


      Format: [a,b,c,d,e]


      a is a number of the form 6n +/- 1
      b is a prime
      c is the largest three smooth number such that a = b + c.
      d is the number of three smooth numbers up to a.
      e is the number of three smooth numbers that were checked until a prime equal to a - c was found.

      Here are the results:


      [5, 2, 3, 4, 1]
      [73, 19, 54, 18, 2]
      [97, 43, 54, 20, 4]
      [409, 193, 216, 31, 5]
      [863, 431, 432, 38, 6]
      [1417, 769, 648, 43, 7]
      [1823, 1439, 384, 46, 15]
      [12869, 9413, 3456, 70, 16]
      [14083, 10627, 3456, 72, 18]
      [18313, 15241, 3072, 75, 22]
      [26759, 22871, 3888, 81, 26]
      [95003, 79451, 15552, 100, 27]
      [107411, 95747, 11664, 102, 33]
      [235729, 211153, 24576, 115, 35]
      [310447, 285871, 24576, 120, 40]
      [537473, 488321, 49152, 131, 41]
      [612341, 577349, 34992, 133, 48]
      [1400771, 1327043, 73728, 148, 51]
      [2125369, 2000953, 124416, 157, 52]
      [2183513, 2059097, 124416, 158, 53]
      [2784223, 2673631, 110592, 162, 59]
      [2969233, 2858641, 110592, 163, 60]
      [6285913, 6049717, 236196, 179, 63]
      [7823449, 7528537, 294912, 184, 64]
      [9570551, 9216257, 354294, 190, 67]
      [12311329, 11979553, 331776, 194, 72]
      [15180509, 14885597, 294912, 200, 80]
      [28232621, 27790253, 442368, 213, 86]
      [32264333, 31984397, 279936, 217, 98]
      [52042369, 51518081, 524288, 229, 99]
      [140505163, 139012171, 1492992, 254, 104]
      [150059783, 148996901, 1062882, 255, 111]
      [338697967, 335711983, 2985984, 276, 112]
      [355088171, 351942443, 3145728, 278, 113]
      [644492893, 640713757, 3779136, 294, 125]
      [885813023, 881831711, 3981312, 303, 133]


      It's interesting to see that no more than half of the available three smooth numbers had to be checked before a prime was obtained. The closest approach to the half way mark was at 32,264,333, when 98 of the 217 possible three smooth numbers were used up before the prime 31,984,397 was reached.


      Will this result be short lived, and is only an example of the infamous law of small numbers at work? Alas the above results alone took about four hours of computer time so it will be hard to check experimentally.

      Mark
    Your message has been successfully submitted and would be delivered to recipients shortly.