Date: Tue, 2 Oct 2012 05:11:58 -0000 (UTC) From: Walter Nissen To: primenumbers@yahoogroups.com Subject: [PrimeNumbers] np ( n ) = n^n + (n+1)^(n+1) ; 2 prominent questions Greetings , all , np ( n ) = n^n + (n+1)^(n+1) has numerous interesting aspects . Two aspects of this expression are prominent . ( 1 ) : The number of prime factors of np ( n ) . The first line in the table of OMEGA below is : 1 1 1 4 2 3 The first 3 counts in the first line are each 1 , because for each of n = 1 , 2 and 3 , np ( n ) = n^n + (n+1)^(n+1) is prime . The last count in the first line is 3 , because 6^6 + 7^7 has 3 prime factors : 11 , 239 , and 331 . t OMEGA ( n^n + (n+1)^(n+1) ) n mod 6 1 2 3 4 5 0 1 1 1 4 2 3 2 3 2 5 2 6 4 2 3 6 3 3 4 6 2 7 3 5 5 3 3 5 3 3 3 7 4 5 4 3 2 2 2 6 3 6 4 5 3 8 6 6 3 5 5 5 5 3 3 5 2 8 4 4 6 6 6 8 8 4 3 4 7 7 6 6 4 4 7 9 6 7 5 9 5 7 4 3 5 6 7 9 3 2 5 4 8 9 5 8 2 4 6 11 6 5 4 3 8 11 4 5 ( on this 18th line : 103 <= n <= 108 ) 6 7 8 7? 6 3? 6 5 6? 11? 7 6 6? 4? 5 7 13 7? 5 7 10? 9 7 9 4 6? 5? 10? 7 3 ___ ___ ___ ___ ___ ___ 19 22 15 32 17 23 total of first 6 lines = 6 periods , 1 <= n <= 36 65 79 81 130 77 82 total of first 18 lines = 18 periods , 1 <= n <= 108 3.6 4.4 4.5 7.2 4.3 4.6 average of first 18 lines It's notable that when n mod 6 = 4 , the number of prime factors is relatively large and when n mod 6 = 1 , the number of prime factors is relatively small and when n mod 6 != 1 or 4 , the number of prime factors is moderate , when n mod 3 != 1 , the number of prime factors is moderate . Perhaps , it's easy to understand the surplus of prime factors for 4 mod 6 , because there are a few known algebraic factors : 3 and ( n^2 + n + 1 ) / 3 ( twice ) . E.g. , 4^4 + (4+1)^(4+1) = 3 * 7 * 7 * 23 ; Richard Guy mentioned this surplus in a private communication . But , in the leftmost column , why are there so few prime factors for 1 mod 6 ? ( 2 ) : It's notable that p | np ( n ) , for certain n mod ( p ( p - 1 ) ) . E.g. , for p = 3 , p(p-1) = 6 , and for n mod 6 = 4 : np ( 4 ) = 4^4 + (4+1)^(4+1) = 3 * 7 * 7 * 23 np ( 10 ) = 3 * 37 * 37 * 8017 * 8969 np ( 16 ) = 3 * 7 * 7 * 13 * 13 * 34041259347101651 The top of the p(p-1) table is : (2 | np ( n ) iff n mod 2 = ) 3 | np ( n ) iff n mod 6 = 4 5 | np ( n ) iff n mod 20 = 1 8 7 | np ( n ) iff n mod 42 = 4 12 16 33 11 | np ( n ) iff n mod 110 = 6 7 20 34 61 62 63 101 13 | np ( n ) iff n mod 156 = 16 22 24 53 86 94 100 147 E.g. , np ( 21 ) = 5 * 69454092876521107983605569601 np ( 28 ) = 3 * 5 * 271^2 * 2360926164108571968813424783598971267 To find factors of np ( n ) , is it possible to compute this table faster than using ECM or NFS ? Over the last decade or so , a number of people have contributed to the pursuit of primality in this expression , to whom I'm quite grateful ; on the math side , notably David Broadhurst , Mike Oakes and some of the usual suspects ; and on the computational side , notably Rich Dickerson , Lionel Debroux ( recently importantly ) , yoyo@home ( recently importantly ) , Andy Steward , GMP-ECM , Primo , msieve and ggnfs ( these lists are inadequate ) . Cheers , Walter --- Here are a few details : The only known prime np are for n = 1 , 2 and 3 . np ( 415 ) is easy to factor , it has only 2 factors and one of them is 29 . ( ! ) np ( 3754 ) has at least 19 prime factors . Using many years of CPU , all np have been completely factored for n <= 111 : http://upforthecount.com/math/nnp2.txt ( unpublished ) The latest updates : http://factordb.com/index.php?query=n^n%2B(n%2B1)^(n%2B1)&n=1&perpage=150 Mind-bending ; states non-trivial facts about numbers too large to represent in the known universe ; but nevertheless , intended for a general audience : http://upforthecount.com/math/nnnp1np1.html Many details : http://upforthecount.com/math/nnp.html ( unpublished ) http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)?&action=Search Many messages right here : http://tech.groups.yahoo.com/group/primenumbers