Conference rusure::math

Here are some computer results.  Many initial numbers lead to numbers larger
that the algorithm was willing to handle (1000000); otherwise, these represent
all the cycles reachable by an initial number less than 60000.

The first number in each line is the smallest number that leads to the cycle,
rather than the smallest number in the cycle.  The last two cycles are curios.
		 n
Pn numbers have f (x) = x.

P1 numbers
6 -> 6
28 -> 28
496 -> 496
8128 -> 8128

P2 numbers
220 -> 284,220
1064 -> 1336,1184,1210,1184
1188 -> 2172,2924,2620,2924
5020 -> 5564,5020
6232 -> 6368,6232
10744 -> 10856,10744
12285 -> 14595,12285
17296 -> 18416,17296
20220 -> 36564,56844,86936,76084,63020,76084
46360 -> 65240,103240,139760,185368,203432,185368

P5 numbers
9464 -> 12496,14288,15472,14536,14264,12496

P28 numbers
5916 -> 9204,14316,19116,31704,47616,83328,177792,295488,629072,589786,294896,
        358336,418904,366556,274924,275444,243760,376736,381028,285778,152990,
        122410,97946,48976,45946,22976,22744,19916,17716,14316

    do any of you know the next number after 8128?
     is there a formula to calculate these numbers?
      I have been playing with this and came up with
              1   2
         6=  2 *(2 -1)     =2   *   3
              2   3        
        28=  2 *(2 -1)     =4   *   7
              4   5
       496=  2 *(2 -1)     =16  *  31 
              6   7
      8128=  2 *(2 -1)     =64  * 127
    
    looking for paterns I notice the next number might end in 496. the
    exponent in () might be prime or odd (but 2 is not odd).any info
    would be helpful. thanx    Galen
     

    would 1 be considered a perfect number?
              0   1
         1=  2 *(2 -1)     =1   *   1
    
    

re: .2:

The general formula for the sequence of perfect numbers is (2^M-1) * 2^(M-1),
where 2^M-1 must be prime.

If M is composite, then so is 2^M-1.  However, M prime does not guarantee
2^M-1 will be prime.  The numbers M for which 2^M-1 is prime are called
Mersenne primes.

The perfect numbers 6, 28, 496 and 8128 correspond to M equal to 2, 3, 5 and 7,
respectively.  The next prime, 11, is not Mersenne, since
2^11-1 = 2047 = 23*89.  However, M=13 is Mersenne, yielding the next
perfect number 33550336.

To the best of my knowledge, no perfect numbers have been discovered aside
from those generated from Mersenne primes.

David Ellis -- Secure Systems Group -- LTN2-2/C08 -- DTN 226-6784 

    All even perfect numbers are in the form given in .4.  The existence of
    odd perfect numbers is uncertain, last I heard.
    
    
    				-- edp 

    According to research some years ago an odd perfect number, if one
    existed, would have to be larger than 10^600.  No new even perfect
    numbers have been found.
    
      John

The following numbers yield Mersenne primes, which in turn yield perfect 
numbers: 2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,
3217,4253,4423,9689,9941,... The last one yields a prime of nearly 3000, and a
perfect number of nearly 6000, digits. The huge gap between 4423 and 9689 is
noteworthy...

Again, Beiler's book mentioned elsewhere is the source.

Lynn Yarbrough 

If M is prime, and 2^M-1 isn't, is it always *almost* prime, that is,
equal to p1*p2 for two primes p1 and p2 ?

/Eric

    It apears to me that    M    (M-1)
                          (2 -1)*2
                           
    will, in binary, always have M ones followed by M-1 zeros
     i.e.    3     (2)
           (2 -1)*2   =28 = 11100
    
             5     (4)
           (2 -1)*2   =496= 111110000
    
             13     (12)
           (2  -1)*2    =33550336=1111111111111000000000000
    is this true?      thanx  Galen

>If M is prime, and 2^M-1 isn't, is it always *almost* prime, that is,
>equal to p1*p2 for two primes p1 and p2 ?

Nope. M=179 is a counterexample; 2^179-1 = 359*1433*<a very large prime>.
Thanks, MAPLE.

Lynn Yarbrough 

    Re .9:
    
    Yes.  2^M is 1 followed by M zeroes.  Subtracting one gives M ones.
    Multiplying by 2^(M-1) appends M-1 zeroes.
    
    
    				-- edp 

    Peter, in my opinion it would be a shame to define "almost prime" in a
    manner that allows for anything more than two factors.  This probably
    comes from my background of trying to "crack" (factor) known composite
    numbers, and not being able to since the factors are so large.
    
    So to me numbers are "almost prime" if their factors are all large.
    For a number N with two factors, "large" is defined to be "greater
    than the cube root of N".  This can be generalized (and a bit of
    humor injected) via the following taxonomy:
    
    N is said to be PRIME if it has no nontrivial factors.
    
    N is said to be CHOICE if N has exactly two distinct prime factors,
    both of which are greater than the cube root of N.
    [Some CHOICE questions are posed below.]
    
    N is said to be GOOD (soon also SELECT) if N has exactly three prime
    factors, all of which are greater than the fourth root of N, and are
    mutually distinct. 
    
    N is said to be COMMERCIAL if N has exactly four prime factors, all of
    which are greater than the fifth root of N, and are mutually distinct. 
    
    N is said to be UTILITY if N has exactly five prime factors, all of
    which are greater than the sixth root of N, and are mutually distinct. 
        
    N is said to be CUTTER if N has exactly six prime factors, all of which
    are greater than the seventh root of N, and are mutually distinct. 
    
    N is said to be CANNER if N has exactly seven prime factors, all of
    which are greater than the eigth root of N, and are mutually distinct.

    For CHOICE numbers -- composites with exactly 2 large factors --
    does anyone know:
    
    [1] Are there an infinite number of CHOICE numbers?
    	[It would seem obvious, but the classic constructive proof for
	primes doesn't help here.]
    
    [2] If the answer to [1] is NO, what is the largest CHOICE number?
    
    [3] If the answer to [1] is YES, are there more CHOICE numbers than
	PRIME numbers?   (I.e., for the interval [1..M] what is the ratio
	of the count of PRIMEs to the count of CHOICEs?  And what is
    	the limit as M --> oo ?)
    
        A semi-random sampling of 254 numbers in the range of 10^28,
        having no factors smaller than 23 initially, revealed:  
        20 PRIMEs, 10 CHOICEs, 3 GOODs, 0 lower-grade numbers.
   

    [1]  Yes.
    
    	- There are an infinity of primes, P(n).
    
    	- Therefore, there are an infinity of numbers C, where C =
	    P(n) * P(m), and P(n) ~= P(m)
    
    	- By the Unique Factorization Theorem, there can be no other
    	    primes which factor C.
    
    	- Therefore, there are an infintiy of choice numbers, C.

    
    --  Barry

>    	- Therefore, there are an infinity of numbers C, where C =
>	    P(n) * P(m), and P(n) ~= P(m)

    Yes, a most excellent observation.  Unfortunately I don't see where
    you can conclude P(n) ~= P(m).  How is this done?

    Recall that the standard proof relies on constructing P(m) = P(n)! + 1
    Clearly in this case P(m) >> P(n).  So I don't see where P(n) ~= P(m)
    is demonstrated.

      John

    OK, terminology check:
    
    	When I say "~=" I mean "not equal to".
    
    Therefore, since there must be an infinity of primes P(n), then there
    must also also exist an infinity of primes P(m) > k, for any k.
    Let k = P(n), then P(m) > P(n), therefore P(m) ~= P(n).
    
    Actualy, now that I think about it, this is not even necessary for 
    the proof.
    
    
    --  Barry

    re.11
     2^M is 1 followed by M zeros
    
    
     then a perfect number could never be odd
        thanx for the replies
     galen

.16>    OK, terminology check:
.16>    
.16>       When I say "~=" I mean "not equal to".

    Check bounced.  I use ~= to mean "approximately equal", and any
    of   <>   #   ^=  \=   to mean not equal.
    
    Back to .16, you have ommitted any proof of one of the necessary
    conditions for being a CHOICE number, namely that both factors
    have to be greater than the cube root of their product.  While
    35 = 5 * 7 is CHOICE; 51 = 3 * 17 is not.  The idea behind CHOICE
    numbers is not just that they have two factors, but that the factors
    are close together (but distinct).
    
    Yes, there are an infinite number of numbers that are the product
    of two distinct primes, but it isn't clear that primes always come
    "close enough together" to make the number CHOICE.

--------------------
        
.17>    re.11
.17>     2^M is 1 followed by M zeros
.17>     then a perfect number could never be odd
    
    The theorem states that EVEN PERFECT NUMBERS HAVE THIS FORM, but
    says nothing about odd perfect numbers.

      John

    Re .18:
    
    I get ~ as "not" from my symbolic logic days (Copi Syntax).
    
    Also, I had forgotten about the C^(1/3) requirement.  Sorry, I'll
    work on it.
    
    
    --  Barry

    For any number n >= 2, there is a prime p such that n < p < 2*n
    (the name or source of this theorem escapes me).

    Let p be a prime, and let q be a prime such that p < q < 2*p.
    Since p > 1, we have (p*q)**(1/3) < (p*p)**(1/3) < p < q.
    Therefore, p*q has two prime factors, each of which is greater
    than the cube root of p*q; that is, p*q is a CHOICE number.

    Along similar lines, we can show that there are an infinite number
    of numbers C such that C has n prime factors, each of which is
    greater than C**(1/n) / 2^((n-1)/2).

    Choose a prime p.  Then it is possible to choose n-1 additional
    primes q, r, s, ..., z such that:

	p < q < 2*p < r < 4*p < s < 8*p < ... < z < 2^(n-1)*p

    Let C be the product of these primes;  we have

	C = p*q*r*s*...z < p*(2*p)*(4*p)*(8*p)*...*(2^(n-1)*p)
		         = p^n * 2^(n*(n-1)/2)

	C**(1/n) < p * 2^((n-1)/2)

	C**(1/n) / 2^((n-1)/2) < p

    If p > 2^(n*(n-1)/2), then we have:

    	C**(1/(n+1)) < p^(n/(n+1)) * 2^(n*(n-1)/2/(n+1))
		     = p * p^(-1/(n+1)) * 2^(n*(n-1)/2/(n+1))
		     = p * (p^-1 * 2^(n*(n-1)/2))**(1/(n+1))
		     < p * (1)**(1/(n+1)) = p

	C**(1/(n+1)) < p

    Thus, we have an infinite number of numbers of all grades.

    Eric Osman pointed out a typo in .20.  It should read:

    Let p be a prime, and let q be a prime such that p < q < 2*p.
    Since p >= 2, we have (p*q)**(1/3) < (2*p*p)**(1/3) <= p < q.
    Therefore, p*q has two prime factors, each of which is greater
    than the cube root of p*q; that is, p*q is a CHOICE number.

Inspired by .13
    
    AM is a program by Doug Lenat which was designed to discover
    interesting mathematical hypothoses.  It managed to discover most
    of number theory up to (if I remember) the mid-nineteenth century.
    It got bogged down trying to find interesting consequences to
    Goldbach's Conjecture.
    
    It discovered a set of interesting numbers defined to be numbers
    with exactly two factors.  This is, of course, simply a slightly
    unusual way of stating the definition of prime numbers.
    
    It found one true non-standard theorem.  At first Lenat claimed
    that it was a new theorem, but it turned out that Ramanujan had
    discovered the same theorem (of course -- it should of gone without
    saying :-).  I don't remember the details, but it involved a
    generalization of that definition of a prime number.  Perhaps numbers
    with a maximal number of factors.  Anyone remember?  I'll look it
    up tomorrow, if no one posts it before I get to it.
    
    					Topher

I have been out of this conference for awhile, and noticed the
AM note this morning while catching up.  I read Lenat's thesis
about five years ago, but I think I can sum up what AM did
mathematically.

AM discovered the set of pairs of primes whose sum is also
prime, and classified it as an interesting set to investigate
further.  That's not the same thing that AM did which Ramanujan
also discovered, but it is an interesting way of defining prime
pairs.

AM arrived at a discovery made by Ramanujan by methods which were
quite different from Ramanujan, according to Lenat.  AM was looking
at the set of numbers which have a high number of divisors.  Let
d(n) be the number of divisors in n.  AM defined an interesting set
to be the set of numbers n s.t. forall(m) where m < n, d(m) < d(n).
It turned out that when you factor all the n into primes, you get
an interesting regularity in the way all n factor out.  I don't think
Lenat said what the regularity was or why it was interesting, other
than the fact that it was a living, breathing real result that AM
came up with by itself.  I think AM also came up with an interesting
geometric interpretation of Goldbach's conjecture, which was the other
highlight of AM's performance.

I don't have the book in front of me, but Lenat's very readable thesis
is reproduced in Knowledge_Based_Systems_in_Artificial_Intelligence,
which used to be available in most college bookstores.  The book is
simply a reproduction two highly original theses from Stanford, Lenat's 
and Randall Davis'.

Dave