Up a LevelClick the arrow to go up a level to the Math Index.
Follow the above link or click the graphic below to visit the Homepage.

HomepageDivisibility of
Cullen Numbers
James Cullen



My introduction to Cullen Numbers came during searches on genealogical material for the site and I came across a mention of a Rev James Cullen after whom the Cullen Numbers are named. He was interested in the divisibility properties of the numbers. A little research turned up a biography, some definitions, and websites related to the search for Prime Cullens. Seeing that we share the same name and that Number Theory is one of my side-interests, I've looked into the Cullen Numbers at some depth and am presenting that material here. Also, I normally sign pages I've authored with 'Jim Cullen' but I've made an understandable exception for this page! The calculations were done almost exclusively on a Texas Instruments Voyage 200 PLT, a programmable graphing calculator with a built-in CAS (Computer Algebra System). For the functions to work as expected, the MODE setting should be in AUTO. Some programs were run on the TI-89 Titanium to free up the V200 for further work. Some tinkering was done on the HP49G+ but nothing fruitful since the keyboard and user RPL programming can be troublesome, to put it nicely.

In the format I'm using, I will at times explain some of the mathematical concepts but at other times I may not. I'm assuming that anyone who finds this page will be initiated on most of the concepts or at least have a running start and an idea of where to search for further information. Program code is provided, where applicable, and is written in TI-Basic. Again, since the code springs directly from the mathematical concepts, I am assuming at least the basic knowledge from the reader and so explanations of program code will be brief. If you're well acquainted with TI-Basic and the mathematical concepts, please feel free to contact me if you feel there are any notable errors or omissions.


Brief Biography of Rev James Cullen

Rev. James Cullen was born April 19,1867 at Drogheda, Co Meath, in Ireland. He studied pure and applied mathematics at Trinity College in Dublin but thereafter sought to become a priest and attended various schools and colleges in England. He was ordained priest at St Beuno's College in North Wales on July 31'st 1901 and continued teaching mathematics to younger Jesuits there and in Derbyshire. In 1905 at St Mary's College in Derbyshire, Rev Cullen originated the study of what we now know as the "Cullen Numbers". He was particularly interested in the divisibilty of the numbers as none of them were found to be prime except the first. In fact, it was not until 1957 that the study of the Cullen Numbers was taken up again and it was discovered and then proven that the the 141'st Cullen Number was also prime. Rev Cullen continued his duties in the priesthood but also contributed mathematical articles for publication in journals such as "Nature" and "The Mathematical Gazette". Rev James Cullen passed away on December 7, 1933.


Summary and Definition of the Cullen Numbers

Cullen Numbers are positive integers of the form Cn = n . 2n + 1, where n is also a positive integer greater than zero. The first five Cullen Numbers are (by substituting in the integers 1 through 5 for n into the equation): 3, 9, 25, 65, and 161. It can be shown that Cullen numbers are almost exclusively composite - prime Cullen Numbers are very rare. The divisibility properties and the determination of which Cullen Numbers are prime numbers is a main attraction and a problem that dates back to their introduction in 1905 by Rev Cullen. From 1957 to the present, only sixteen Cullen Primes are known to exist and they are when n = 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, and 6679881. These results, due to the sheer power needed to prove primality of such large integers, were not possible until the introduction of electronic computing devices. The largest known prime Cullen number C6679881, discovered in August 2009, weighs in at 2,010,852 decimal digits. It is conjectured but not yet proven that there are an infinite number of Cullen Primes and it is also unknown whether or not n and Cn can be simultaneously prime. Very briefly, for those not sure of the definition of a prime number, take a look at C5 = 161 above. The fifth Cullen number equals 161 and is NOT a prime number because 161 = 7 . 23. In simple terms, prime numbers cannot be "broken down" into factors like 161 can be. A number like 23 IS prime because there are no numbers you can multiply together to obtain 23 - thus a number with no factors is known as a prime number.

Calculation of Cullen Numbers is relatively simple but, since the integer value increases so quickly with n, there is a limit as to how high an exact integer value for a Cullen Number may be calculated. Since the maximum size of an integer on the TI V200 is 614 decimal digits, the maximum Cullen Number that may be exactly represented is C2029. If we allow for exponential notation, the calculator will continue to return values up to C3310, which is given as 8.49402708616 EE+999. The code for the user function cullen(n), which limits the argument to those which have an exact representation on the calculator, is given below:

N'th Cullen Number
:cullen(n)
:Func
:If n>2029:return "overflow"
:n*2^n+1
:EndFunc



Cullen Numbers can also be expressed as a recurrent series and so share some properties with other series. The expression for the Cullen Numbers in this form is:

Cn = 4 . ( Cn-1 - Cn-2 ) + 1

To see how this works, calculate Cn = C3, given that Cn-1 = C2 = 9 and that Cn-2 = C1 = 3.
Then find that C3= 4.( C2-C1 )+1 = 4.( 9-3 )+1 = 25, which is correct; C3 = 25.


1) Number of Digits in a Cullen Number and Other Miscellany

1a) Number of Digits in a Cullen Number Cn
More as a matter of curiosity than anything, the number of digits in a Cullen Number Cn is easily determined by taking the ceiling of the log base ten of the equation for the Cullen Numbers. There are times when this type of calculation can be in error by one digit but, since curiosity is the only reason for calculating it at all, this simple rule is good enough.

log10(n . 2n + 1) = log10(n) + n . log10(2)

and I've disregarded the trailing "+1" for simplicity's sake. Take for example the above list of Prime Cullens. The number of digits in C141 = 45. The number of digits in C1354828 = 407,850. It's no surprise that the Cullen Numbers, containing an exponential, grow very large very quickly. This, coupled with the fact that so few Cullen Numbers are prime at all, explains why there are only sixteen Cullen Primes known at present. You may use the following function to calculate the number of digits in any Cullen Number:

Decimal Digits of N'th Cullen Number
:cdgts(n)
:Func
:ceiling(log(n)+n*log(2))
:EndFunc



1b) Repetition of the Final Digits of Cullen Numbers
The final digits of Cullen Numbers repeat in a predictable manner. For example, the pattern of the last digits of consecutive Cullen Numbers repeats in cycles of twenty. The pattern is:

{ 1,3,9,5,5 - 1,5,7,9,9 - 1,9,3,7,7 - 1,7,5,3,3 }

I've split up the cycle of twenty into four cycles of five for a reason. The Cullen Numbers are rich with patterns and here we can see them directly. Cullen Numbers congruent to 0 mod 5 end with a one. Two consecutive Cullen Numbers congruent to 3 and 4 mod 5 repectively, share the same last digit. Of course all Cullen numbers are odd and so end in 1, 3, 5, 7, or 9, and it is equally probable that a given random Cullen Number will end in any particular odd digit.

The cyclic patterns extend beyond just the final digit. Any number of final digits, which we will here refer to as D, results in a pattern with a predictable cycle length we will call LD. Two final digits results in a pattern of length LD = 100. Three final digits results in a pattern of length LD = 500. Four final digits results in a pattern of length LD = 2500, and so on. . . each additional digit results in a pattern five times larger than the previous one. So in general, for any number of final digits we may wish to consider, we have:

LD = 4 . 5D

There is one catch to this pattern of final digits; the pattern does not extend all the way down to C0 unless you are considering just one final digit. If you wish to consider two or three final digits, their pattern only extends down to C2. If you wish to consider four or five final digits, their pattern only extends down to C4. If you wish to consider six or seven final digits, their pattern only extends down to C6. In other words, if the final number of digits in question is an even number D, then the cyclic pattern begins at CD. If on the other hand D is an odd number, then the cyclic pattern begins at CD-1.


1c) Summations Involving the Cullen Numbers

Here are given several straight forward summations involving the Cullen Numbers. The derivations themselves are equally direct and so only the results are given. The first is a simple sum of all Cullen numbers from 1 to k:

k 
Cn    =    2 . ( k - 1 ) . 2k + k + 2
n = 1 

and you would of course add one to the above result if you wanted the summation to begin at C0=1. Applying a modulus to the above formula for the summation yields a few interesting results such as the fact that the sum of any six consecutive Cullen Numbers results in an integer that is itself divisible by six. In this case, the sum divided by six is found to be equal to (21.k+86).2(k-1)+2, where k is the index of the first Cullen Number in the summation.

The following summations are for the even and odd indexed Cullen Numbers respectively:

Even Cullen Numbers   
k 
C(2n)    =    [ ( 24k - 8 ) . 4k + 9k + 17 ] / 9
n = 0 
 

Odd Cullen Numbers   
k 
C(2n+1)    =    [ ( 48k + 8 ) . 4k + 9k + 19 ] / 9
n = 0 



2) Calculation of Cn mod p

As large as Cullen numbers can be, it's actually a quick and easy task to calculate any Cullen Number to a prime ( or any other ) modulus. Primarily, I'll be concerned with a prime modulus. The standard rules of modular arithmetic apply and we need to calculate:

n . 2n + 1   mod p   where p is an odd prime

Numerically, we can use the modpwr(2,n,p), modular exponentiation function, to obtain an intermediate result and then take the rest of the expression to mod p:

cmod(n,p) = mod( n * modpwr(2,n,p) + 1, p)

and remember that, since p is prime and so coprime to 2, we may reduce the exponent mod phi(p), where phi(p) is Euler's Totient function. Since p is prime, phi(p) = p-1. If n is less than p already, don't bother. Any trick though, to reduce the exponent for the sake of speed, is fair game. Here I use only the standard modular exponentiation function. In the end result, if cmod(n,p) = 0, then Cn is divisible by p, if you're interested in the results for testing divisibility of Cullen Numbers. The code for the functions cmod(n,p) and modpwr(a,b,m) is given below. Note that the character " -> " denotes the calculator's "STO" button for storing a result into a variable:

Cn mod pMod Exp: ab mod m
:cmod(n,p)
:Func
:mod(n*modpwr(2,n,p)+1,p)
:EndFunc
:modpwr(a,b,m)
:Func:Local z
:1 -> z:If b=0:return z
:Loop
:If mod(b,2)=1:mod(a*z,m) -> z
:int(b/2) -> b
:If b=0:Return z
:mod(a^2,m) -> a
:EndLoop
:EndFunc



3) Trial Factoring for Cullen Primes

In the case that you'd like to try your hand at a simple prime sieve for Cullen Numbers, it's really not much different than trial-factoring regular integers. Here's a few tips. Instead of testing divisibility of Cullen Numbers one prime number at a time using slow TI-Basic looping statements, use the very fast built-in Greatest Common Divisor function on the product of a whole group of primes. If the greatest common divisor of a Cullen Number and a product of primes is greater than one then the Cullen Number cannot be prime since it shares factors ( and therefore HAS factors ) with a product of primes. I have taken the product of all the primes less than a thousand and broken the product up into four pieces which I have stored in integer variables called pp1, pp2, pp3, and pp4. The details are as follows:

pp1: Primes from 2 through 47 whose product is 18 decimal digits.
pp2: Primes from 53 through 199 whose product is 65 decimal digits.
pp3: Primes from 211 through 499 whose product is 125 decimal digits.
pp4: Primes 503 through 997 whose product is 210 decimal digits.

Note that 2 is included in the pp1 prime product even though no Cullen Number can be divisible by two. The reason is that these variables serve other purposes besides the calculations meant for Cullen Numbers. Notice also that pp1 is an integer of only 18 digits ( the actual value is 614889782588491410 ). This is because the smaller primes have a much greater chance of being factors of Cullen Numbers. In fact, one-third of all Cullen Numbers are divisible by three; one-fifth of all Cullen Numbers are divisible by five; one seventh of all Cullen Numbers are divisible by seven; and so on. The majority of composite Cullen Numbers are detected by the quick modular calculation using an integer that's only 18 decimal digits long. If compositeness is not detected, then we can take more time for a careful inspection and steadily increase the prime product ( pp2, pp3, pp4 ) used in the GCD calculation. This is another advantage of using four separate prime products - you have the option of choosing when to quit trial factoring!

I will mention here one point involving the actual calculation. Since you can't use the GCD calculation on the expression defining the Cullen Numbers since the size of the integers would overflow the calculator, make use of the following:

If a and b are positive integers with a greater than b

Then GCD( a , b ) = GCD( a mod b , b )

What this amounts to in the coding is simply applying cmod(n,pp1) first and then taking the GCD of the result with pp1. The code below provides the full Cullen Number trial-factoring routine and a simple program to fill the contents of pp1, pp2, pp3, and pp4 using TI's built-in isPrime(x) function, which returns 'true' if x is prime and 'false' if x is not a prime. Likewise, culltst(n) returns 'true' if Cn is a prime candidate due to the trial factoring results. The test returns 'false' if Cn is found to have factors - in which case it cannot be a prime number.

Fill Prime VariablesCullen Trial Factoring Function
:fillpp()
:Prgm:Local p
:7 -> p:210 -> pp1:1 -> pp2:1 -> pp3:1 -> pp4
:Loop:If p>46:Exit:p+2 -> p
:While not isPrime(p):p+2 -> p:EndWhile
:pp1*p -> pp1:EndLoop
:Loop:If p>198:Exit:p+2 -> p
:While not isPrime(p):p+2 -> p:EndWhile
:pp2*p -> pp2:EndLoop
:Loop:If p>498:Exit:p+2 -> p
:While not isPrime(p):p+2 -> p:EndWhile
:pp3*p -> pp3:EndLoop
:Loop:If p>996:Exit:p+2 -> p
:While not isPrime(p):p+2 -> p:EndWhile
:pp4*p -> pp4:EndLoop:Disp "Done"
:EndPrgm
:culltst(n)
:Func
:If gcd(pp1,cmod(n,pp1)) > 1:Return false
:If gcd(pp2,cmod(n,pp2)) > 1:Return false
:If gcd(pp3,cmod(n,pp3)) > 1:Return false
:If gcd(pp4,cmod(n,pp4)) > 1:Return false
:Return true
:EndFunc



4) Divisibility Properties of Cullen Numbers

Given that Cullen Numbers grow so rapidly with n and that factorization itself is a difficult task, it's a wonder that we have as much done as we do in Cullen Number factorization. There are known divisibility properties that help. Here are two divisibility properties, derived from Fermat's Little Theorem, that will come in handy:

Let N = 2 . n - 1     If N is a prime that is congruent to 3 or 5 mod 8 , then Cn is divisible by N.

and it's companion property (which proves to be slightly less useful):

Let N = ( 2 . n + 1 ) / 3     If N is a prime that is congruent to 1 or 7 mod 8 , then Cn is divisible by N.

One of the most basic and useful divisibility properties is this:

If p is an odd prime, then Cp-1 and Cp-2 are divisible by p.

where "odd prime" means any prime number greater than two. A simple proof of this can be found by setting n=p-1 or n=p-2 in the expression n . 2n + 1 for Cullen Numbers and then solving the congruency. We get, if n=p-1, -2p-1 + 1 mod p. Since 2p-1 mod p is congruent to one, we have just (-1)+(+1) which is simply 0 mod p, meaning that Cp-1 mod p = 0. The proof for the case Cp-2 mod p is similiar. I find this property extremely interesting and wondered whether there are other Cullen numbers divisible by a given prime p. Well, of course there are! The question is finding and explaining them. I find that there are regularly placed pairs of Cullen Numbers with a scattering of Cullen Numbers in between that are all divisible by p, a pattern that continues off to infinity. All Cullen Numbers that are divisible by a given prime p, appear in recurring blocks in a cyclic pattern. The size of the repeating pattern is given by Bp which depends on the value of p and p's congruency ( mod 8 ) as follows:

If p is congruent to 1 or 7 mod 8   then   Bp = p . ( p-1 ) / 2

If p is congruent to 3 or 5 mod 8   then   Bp = p . ( p-1 )

We can use this definition of Bp immediately to determine the locations of two consecutive Cullen Numbers divisible by a given prime p, as follows:

If p is any odd prime and k is an integer greater than or equal to zero:

Let n = p + k . Bp       k = { 0, 1, 2, 3, ...}

Then p divides Cn-1 and Cn-2

As an example, suppose p = 11, which is congruent to 3 (mod 8). This means that Bp = p . ( p-1 ) = 11 . 10 = 110. If k is set to zero in the above equation then we have our basic divisibility property which states that Cp-1 and Cp-2 are divisible by p. If k = 1, then n = p + k . Bp  =  11 + 1 . 110 =  121. We should then find that C119 and C120 are both divisible by 11. Since these Cullen Numbers are small enough to work with on the calculator we perform the division and find that:

C119 = 11 . 7189915068109317676161501826061863843   and

C120 = 11 . 14500669044926354977132440657603759011

This rule holds for all values of k and locates ALL such pairs of Cullens divisible by p as the value of k goes to infinity. There are other Cullen Numbers divisible by p besides those pairs identified above. There are also other divisibility properties and some very powerful algebraic factorizations not discussed here that cover some of them. One I will mention, since it proves useful later on, is the following general divisibility property:

If p is an odd prime, then p divides Cm(k) where:

m(k) = ( 2k - k ) . ( p-1 ) - k     for all k >= 0

When I first started plugging values of k into this equation, I found that it missed all the pairs mentioned above. The values for m(k) grew so large so quickly that it skipped over tens then hundreds then thousands of Cullens. In fact, it also seemingly randomly skipped huge numbers of known Cullens divisible by a given p ... or did it?


5) Divisibility of Cullen Numbers using Index mod Bp

Since we find that two consecutive Cullen Numbers divisible by a given prime p can be easily located using the definition of Bp, it's only logical to look at ALL Cullen Numbers divisible by a given prime p and find the congruency of the index mod Bp. By index I mean the argument for the function defining the Cullen Numbers. For example, we know that C5 = 161. In this case, 5 is the index and 161 is the value of the fifth Cullen Number. Referring to a Cullen Number by its index is more convenient due to the extreme size of the value of the Cullen Number itself, especially for large indexes. Now, if there were only a way to test divisibility based on index alone, the mathematics would be much easier to work with.

What we find is that ALL Cullen Numbers divisible by a given prime p, when their indexes are taken mod Bp, repeat in a predictable pattern. The examples given here are for the first eight odd prime numbers, namely; 3, 5, 7, 11, 13, 17, 19, and 23 but the principles apply for any prime number p. The table below lists these first eight odd primes, their associated block sizes Bp, and a list of the indexes mod Bp where a Cullen Number is found to be divisible by that prime number.

pBpList of all ( n mod Bp ) where Cn is divisible by prime p#Terms (Tp)
36{ 1, 2 }2
520{ 3, 4, 6, 17 }4
721{ 5, 6, 10 }3
11110{ 6, 9, 10, 18, 24, 45, 47, 52, 71, 103 }10
13156{ 4, 7, 11, 12, 22, 41, 57, 66, 97, 99, 140, 146 }12
17136{ 15, 16, 19, 25, 30, 52, 77, 106 }8
19342{10,12,17,18,34,61,87,116,119,128,139,149,153,184,199,212,273,312}18
23253{ 5, 7, 21, 22, 34, 42, 83, 107, 125, 135, 178}11

A few observations on these results. The number of items in each list is just B/p, which we will from here on refer to as Tp. In other words; if p is congruent to 1 or 7 mod 8, then there are (p-1)/2 items in the list. If p is congruent to 3 or 5 mod 8, then there are (p-1) items in the list. In either case, Bp divided by the number of items equals p, so we see that if p is an odd prime, then 1/p Cullen Numbers are divisible by p. This is the same ratio as for normal integers though the spacing of the divisible numbers is not a constant for the Cullen Numbers. Notice also that within each list there are two consecutive numbers in bold print which represent the two consecutive Cullen Numbers divisible by p. The above chart, when extended to include larger and larger primes, is absolutely loaded with relations and patterns. I've spent much time going over the tables for more information concerning the Index numbers of the Cullen Numbers and what information can be gleaned from them regarding factors and primality of the Cullen Numbers.

I'll provide an example before we continue. What I've found is that there is an entire set of new divisibility properties similiar to the ones we already have. They were derived by substituting in values for k and restating the results as a new divisibility property: Some examples are, for k = 0, 1, 2, 3, and 4 respectively:

Let N = ( n + 1 ) / 1     If N is prime, then Cn is divisible by N.

Let N = ( n + 2 ) / 1     If N is prime, then Cn is divisible by N.

Let N = ( n + 4 ) / 2     If N is prime, then Cn is divisible by N.

Let N = ( n + 8 ) / 5     If N is prime, then Cn is divisible by N.

Let N = ( n + 16 ) / 12     If N is prime, then Cn is divisible by N.

The general statement can be made that:

Let N = ( n + 2k ) / ( 2k - k )     with k = { 0, 1, 2, 3, . . . }     Then,

If N is prime, then Cn is divisible by N.

These results are entirely useful and interesting and I have not seen them stated anywhere else. I'm really surprised that these haven't been found independently before. Once the results are charted into the tables above, the pattern becomes very clear. Note that when k = 0 and when k = 1, we have our basic divisibility property that states; if p is prime, then p divides Cp-1 and Cp-2. Later we will make use of these divisibility properties to improve the sieve for Cullen Primes. Note also however, that as k increases, the potential for the property to uncover factors of Cullen Numbers decreases significantly, so large values of k of little interest for our purposes.

With some precalculation using the general divisibility property, we now have a method of determining divisibility using the lists from the above table. For example, suppose we want to determine whether or not C2201 is divisible by 19. We know that B19 is 342 and so we calculate 2201 mod 342 and find it is congruent to 149. Since 149 appears in the list of allowed n mod B for p=19 in the table above, we can say that C2201 is divisible by 19. This can be confirmed by calling up the modular function defined earlier and finding that cmod(2201,19) = 0, showing again that C2201 has 19 as a factor. The reason the calculation is faster using the table above is because using the cmod(n,p) function requires a modular exponentiation, where the table requires only modular reduction. For the task of sieving large groups of Cullen Numbers by a given prime p, the time savings can be significant, even allowing for the precalculation.

There are a couple options for the precalculation. One is two calculate cmod(n,p) for all Cullen Numbers from C1 through CB and store the index in a list for all Cn for which cmod(n,p) is congruent to zero. This requires Bp modular exponentiations, which is fine for smaller primes. As we begin working with higher values values of p, we find we are wasting many modular exponentiations as there are only a few results congruent to zero. Ideally, we would like to be able to calculate only those indexes that produce results congruent to zero. I've found there is a way.

We begin with a modification of the general divisibility property given in the previous section. All we've really done is to take the values mod Bp as follows:

If p is an odd prime, then p divides Cm(k) where:

m(k) = [ ( 2k - k ) . ( p-1 ) - k ]      mod Bp       { for all k from 1 through Tp }

The result is that m(k) mod Bp, as k goes from 1 to Tp, produces only those results contained in the list. Since m(k) produces only those indexes representing Cm(k) divisible by p, it's not surprising that m(k) mod Bp also cycles through the list repeatedly. We can calculate this list now with only Tp modular exponentiations. This is an enormous improvement but with one minor hitch - the results are returned in a different order. For example, let p = 23 and let k go from 1 to 11. The results, stored in a list, are:

{ 21, 42, 107, 7, 83, 5, 125, 135, 178, 34, 22 }

Compare this to the results from the above table, which are in numerically ascending order:

{ 5, 7, 21, 22, 34, 42, 83, 107, 125, 135, 178}

The obvious workaround is to reorder the list, which is easy enough to accomplish, but of course requires some time for the calculator to do, especially for larger values of p. It isn't strictly necessary to sort the list for a simple lookup table but the mklist(p) program does so for your benefit should you like to inspect the list of numbers. The programs below will allow you to experiment with this method of testing divisibility of Cullen Numbers by primes. Be aware that trying to test divisibility by large prime numbers can result in excessively long execution times! I've prevented primes larger than 500 from being used in the test (which I suppose you may disable if you really want to). Execution time for primes near 500 is just under 30 seconds. The mklist(p) program, if developed more, could be a bit faster if I were to use the modpwr(a,b,m) function. Since this is just a demonstration program and is actually faster as is with small primes, I left that calculation as a simple exponential. The first program, mklist(p), performs the precalculation by creating a string variable called clist in the Main folder of the calculator. Variable clist contains a string representation of all n mod Bp for which Cn is divisible by p. The list is stored as a searchable string for use with the built-in inString(var,arg) function. The program also stores Bp into the integer variable blist. The function testdiv(n) performs the same basic function as cmod(n,p) introduced in Section 2, but using the contents of clist to determine divisibility of Cn by p instead of performing modular exponentiations.

Create blist & clist for pTest Cn Divisible by p
:mklist(p)
:Prgm
:ClrIO:Local t,k
:If p>500 Then:Disp "Argument is TOO big!":Pause:ClrIO:Stop:EndIf
:If not isPrime(p) Then:Disp "Argument must be a prime number!":Pause:ClrIO:Stop:EndIf
:(p-1) -> t
:If abs(4-mod(p,8))=3:t/2 -> t
:t*p -> blist
:seq(mod((2^k-k)*(p-1)-k,blist),k,1,t) -> clist
:SortA clist
:string(clist) -> clist
:","&mid(clist,2,dim(clist)-2)&"," -> clist
:Disp "Finished":Pause:ClrIO
:EndPrgm
:testdiv(n)
:Func
:If inString(clist,","&string(mod(n,blist))&",")=0:Return false
:Return true
:EndFunc

As an example of how fast this method can work, I performed the precalculation for p = 491, which took about twenty seconds. I then ran testdiv(n) to find out if C29702468866000 ( a Cullen Number with almost 9 trillion decimal digits ) was divisible by 491. The function returned true (as it should have) in approximately 0.158 sec, according to the timing utility provided by Bhuvanesh Bhatt. The regular cmod(n,p) function returned the result congruent to zero (as it should have) in about 2.368 sec. Yes, the program is just a demo - yes, 491 is a relatively small prime number, but it does demonstrate an almost 15 times speed improvement.


6) Example: Divisibility by Index Without Precalculation

It becomes clear that there is a bottleneck when it comes to determining divisibility of Cullen Numbers by larger and larger primes using a list-type lookup table described in the last section. The precalculation required can quickly grow to an unreasonable size. Consider a potential prime factor p = 134625781, which is really not as unreasonable as you may think - sieving programs typically sieve, or perform trial-division, into the billions during the process of searching for prime Cullen Numbers. Note that 134625781 is congruent to 5 mod 8 so that we need to precalculate, store, and perform searches on, a list of ( p-1 ) = 134625780 items. This is not very desirable, and not just because of the memory and cpu requirements to handle the list. Sieving ranges are typically only in the tens of thousands of prime candidates at a time and one quickly approaches the point where there is no time savings at all using a lookup table for determining divisibility of Cullen Numbers.

Can the divisibility test be performed without the precalculation? Yes but, the complexity of doing so is just about the same complexity of performing the cmod(n,p) = 0 test. It's not likely that any algebraic manipulation of the numbers would magically give you the required information without having to perform at least one modular exponentiation, the same as required by the cmod(n,p) = 0 divisibility test. If this were not so, then prime numbers would not be the mystery that they are. An example illustrates this.

In Section 4 there was given a general divisibility property:

If p is an odd prime, then p divides Cm(k) where:

m(k) = ( 2k - k ) . ( p-1 ) - k     for all k >= 0

and it's modification in order to calculate the list of n mod Bp such that Cn is divisible by p:

If p is an odd prime, then p divides Cm(k) where:

m(k) = [ ( 2k - k ) . ( p-1 ) - k ]      mod Bp       { for all k from 1 through Tp }

We have the ability to, in effect, work this property in reverse. That is, determine the value of k required to be added to n in order that the result is divisible by ( p-1 ), then divide by ( p-1 ) and add the value of k again. Take this result to mod p. Then check whether two raised to this particular value of k, taken to mod p, results in an equal value:

Given n       let     k = p - 1 - [ ( n mod Bp ) mod (p-1) ]

Then if       [ ( n mod Bp + k ) / ( p - 1 ) + k ] mod p = 2k mod p

Then       Cn is divisible by p.

which is clearly a convoluted method of determining the divisibility of a Cullen Number Cn by a given prime p and, if p is even moderately large, a modular exponentiation will be required anyways to determine divisibility. I didn't even bother to write any program code for the above method. Such a calculation would be almost ridiculous to perform given the simplicity and effectiveness of the cmod(n,p) formula. For small prime test divisors however, the lookup based on the index mod Bp is still a good option.


7) Improving the Prime Cullen Sieve with Divisibility Properties

The goal of the Cullen Prime Sieve is to eliminate prime candidates by showing that a given Cullen Number has factors. So far we've implemented only a basic prime sieve by checking Cullen Numbers for divisibility by prime numbers less than 1000. If you inspect the factorizations of Cullen Numbers however, you'll find that very large factors are very common. It is not practical to check for divisibility by primes of this size so we need another way to show a Cullen Number has factors without actually testing for divisibility directly.

One way to do this is to try working the divisibility properties in reverse. As an example, I'll demonstrate this concept using the simplest and most useful property:

If p is an odd prime, then Cp-1 and Cp-2 are divisible by p.

Suppose we want to determine whether or not C40 can be eliminated as a prime candidate by showing it has factors. If we note that 41 is a prime number, we can set p = 41 and state that Cp-1 and Cp-2 are divisible by p; or that C39 and C40 are divisible by 41. We can then eliminate C40 as a prime candidate since we have identified at least one factor; C40 is divisible by 41. What we can do with this idea is to check whether a given Cullen Number is one of the two possible Cp-1 or Cp-2 that cannot be prime since they are divisible by p. We can say then that:

If either (n+1) or (n+2) is prime, then Cn cannot be prime.

The isPrime(x) function on the TI V200/92+/89 line of calculators is a fast and reliable method of implementing this concept and so the following line of code may be added to our Cullen Trial Factoring Function culltst(n):

If isPrime(n+1) or isPrime(n+2):Return false

Since this is basically a conditional sieve with primes that are just as large as the index of the Cullen Numbers we are checking, this is an excellent method to add on to our sieving function - especially for large Cullen Number indexes. We just need to make note of the fact that the density of primes tapers off at high values of n and so we can expect to see some drop in effectiveness in our sieving function.

While we're at it we may also want to make use of the two divisibility properties given in Section 4:

Let N = 2 . n - 1     If N is a prime that is congruent to 3 or 5 mod 8 , then Cn is divisible by N.

Let N = ( 2 . n + 1 ) / 3     If N is a prime that is congruent to 1 or 7 mod 8 , then Cn is divisible by N.

For example, consider the first divisibility property. We need to check not only that 2.n-1 is a prime number, but also that this prime is congruent to 3 or 5 mod 8. As an example, we'll perform the check on C283474 to find out if this Cullen Number may have any factors that can be discovered using the above property. We set N = 2.(283474)-1 = 566947. Applying isPrime(566947) the calculator returns true, and we find that mod(566947,8) = 3 so we may conclude that C283474 is divisible by 566947, which is pretty quick work for a number with over 85,000 decimal digits! We can confirm this afterwords by noting that cmod(283474,566947)=0. The following section of code may be added to our Cullen Trial Factoring Function culltst(n). In general, while programming in TI-Basic, it is recommended that you avoid the use of local variables whenever possible for the sake of speed. In this case however, I make use of a temporary variable t in order to prevent having to calculate a value twice.:

2*n-1 -> t:If isPrime(t) and abs(4-mod(t,8))=1:Return false
(2*n+1)/3 -> t:If isPrime(t) and abs(4-mod(t,8))=3:Return false

which turns out to work very well with the only concern is the unavoidable tapering off of effectiveness for large values of n due to the nature of the density of primes. I will demonstrate shortly what I mean by "effectiveness" and how it impacts the programming of these tests.

What we'd like to do first though is to expand on the idea of actually targeting primes as potential factors instead of sieving with primes at random. Since we have quite a few tests to try on Cullen Numbers now, I've tried to implement some ideas into programming code which will cover more than one test at a time. Recall the general divisibility from Section 4:

If p is an odd prime, then p divides Cm(k) where:

m(k) = ( 2k - k ) . ( p-1 ) - k     for all k >= 0

By taking advantage of this property we can not only eliminate one of our other tests, but we can also speed up the test in the process. In addition, we are able to uncover factors not obtainable otherwise besides with brute force and inordinate amounts of time. As an example, I implemented all the tests we've put together at this point ( plus one test not covered in this article ) and ran the test from C1354800 to C1354899. I already know that the only Cullen Prime in the range is Mark Rodenkirch's record Cullen Prime - C1354828 - currently the largest discovered. This test then covers a range of a hundred and, after running the test, there were still ten Cullen Numbers for which no factors could be found. They were when n was equal to:

{ 1354816, 1354827, 1354828, 1354829, 1354845 }

{ 1354860, 1354878, 1354889, 1354893, and 1354896 }

Using the above general divisibility property, I was able to quickly demonstrate that two of these Cullen Numbers are composite by providing a factor:

C1354827   is divisible by   270967   and,

C1354878   is divisible by   677441

which can be confirmed by noting that cmod(1354827,270967)=0 and cmod(1354878,677441)=0.

To make the general divisibility property work for us, we first assume that there is a prime number p which divides Cn and satisfies the divisibility property for some value of k. We then carry out the calculation with assumed values of k, drawing out the resulting values of p and testing them for primality. If any p is prime, then p divides Cn. The value of k is increased until either a factor is discovered or until the resulting value of p falls below that which was already tested in the basic prime sieve. Rather than try to explain, here is the algorithm for the test:

Given Cn, let k = { 0, 1, 2, 3, . . . } and let r = ( 2k - k )

If ( n + k ) mod r is congruent to zero then test:

If (( n + k ) / r ) + 1   is a prime number p,

Then Cn is divisible by p

Although the algorithm may be a bit convoluted, it is the direct result of working the general divisibility property in reverse. Since there are no modular exponentiations and the integer divisions are small, the algorithm is very very fast for what it does. When k = 0 and k = 1 in the equations, we are actually performing the check for the divisibility property that states:

If p is an odd prime, then Cp-1 and Cp-2 are divisible by p.

since, when k = 0, we are checking that n + 1 = p; and, when k = 1, we are checking that n + 2 = p. Another nice thing about this is that the loop terminates after just one isPrime(x) function execution if a prime factor is found where the old method automatically requires that we perform isPrime(x) twice.


8) Extended Divisibility Properties of Cullen Numbers

It is possible to immediately extend some of the known divisibility properties of Cullen Numbers by recognizing the fact that n, for all Cullen Numbers Cn divisible by a given prime p, are congruent to a fixed set of values mod Bp. In other words, if we have enough information, we can make use of the cyclic nature of some divisibility properties in order to uncover divisors of Cullen Numbers. In practice however, this method has very limited value. Solving can be complex and the resulting factors are small compared to the value of the index. I give one example below.

In the examples in the previous section, we made use of the general divisibility property by solving the equation for mk for prime p while allowing the value of k to have successive increasing values. In general, k can be said to represent the number of cycles of Bp in the equation, with each cycle containing another potential factor. We are able to do this but only if certain values of n mod Bp are immediately known. For example, results from Section 4 state that:

If p is any odd prime and k is an integer greater than or equal to zero:

Let n = p + k . Bp       k = { 0, 1, 2, 3, ...}

Then p divides Cn-1 and Cn-2

Not only can we perform the basic check on whether n+1 or n+2 is a prime number p, but we can also check to see if maybe n+1 or n+2 is a multiple of Bp added to a prime number p. We have to remember that the value of Bp depends on the value of p mod 8. The result is four new solution sets for p; the solutions involving n+1 or n+2 can result in values for a prime number p such that p is congruent to plus or minus 1 mod 8 or congruent to plus or minus 3 mod 8. We should be aware that there are decreasing odds of uncovering prime factors of Cn with increasing values of k in the above equation. Not only that, but there is the fact that we are inspecting only two possible cases of divisibility out of perhaps millions, if p is a very large prime.

We will expand the above equations for the case of n+1 being a possible multiple of Bp added to p, for both cases of p mod 8, as follows:

Case: p = +/- 1 mod 8Case: p = +/- 3 mod 8
n+1 = p + k . p . ( p-1 ) . 1/2n+1 = p + k . p . ( p-1 )
n+2 = p + k . p . ( p-1 ) . 1/2n+2 = p + k . p . ( p-1 )

which we then rearrange to solve for p, taking only the positive solution of the quadratic:

Case: p = +/- 1 mod 8Case: p = +/- 3 mod 8
p= [ sqrt(8.k.n + (k+2)2) + k-2 ] / (2.k)p= [ sqrt(4.k.n + (k+1)2) + k-1 ] / (2.k)
p= [ sqrt(8.k.n + k.(k+12)+4) + k-2 ] / (2.k)p= [ sqrt(4.k.n + k.(k+6)+1) + k-1 ] / (2.k)

As expected, when k=0 in any case, we find that, if either n+1 or n+2 is a prime number p,then Cn is divisible by p. Another useful result, which also holds true for any case, is the following:

If either (n+1) or (n+2) is the perfect square of a prime number p,

Then Cn is divisible by p.

This is easily confirmed and, when you look again at the equations this result was derived from, not entirely surprising. In fact, it can be shown that if n is any perfect power of any prime p, then both Cn-1 and Cn-2 are divisible by p. This is due to results obtained when one defines the necessary properties of the factors of n in order that Cn-1 and Cn-2 are divisible by one of the factors of n. One can then quickly show why both C47 and C48 are divisible by 7; because 49 is the perfect square of the prime number 7. One could also quickly show why both C6887 and C6888 are divisible by 83; because 6889 is the perfect square of the prime number 83. Likewise, both C341 and C342 are divisible by 7; because 343 is a perfect power of the prime number 7, in this case, 343 = 73. Testing for such conditions can be difficult and, at any rate, perfect squares of primes are rare enough, not to mention higher powers of them. Such tests would be of little benefit.

If we only consider the cases where k<3 then there is one other divisibility property that may be of some use in discovering prime factors of Cn:

Let r = 8 . ( n+1 ) + 1   or 8 . ( n+2 ) + 1. If r is a perfect square then test:

If p = [ sqrt( r ) + 1 ] / 4   is a prime congruent to 3 or 5 mod 8

or If p = [ sqrt( r ) - 1 ] / 2   is a prime congruent to 1 or 7 mod 8

Then Cn is divisible by p.

For example, by the above, we could show that C1126 or C1127 is divisible by 47, or that C13693 or C13694 is divisible by 83. Can you see the pattern here? It's the cycle showing. You will find that, in the two examples just presented, (n+1) or (n+2) mod Bp = p. Although the properties are somewhat useful, you immediately see that the size of the prime factors are fairly small compared to the sizes of the indexes of the Cullen Numbers they are factors of. This becomes even more apparent as k increases, so they are of little use to us beyond k=2 in this case. There is another approach to this problem in general and leads to the idea of uncovering factors of Cullen Numbers by examining the factors of the indexes of Cullen Numbers instead.


9) Divisibility by Factoring Indexes of Cullen Numbers

Divisibility of Cullen Numbers according to the prime factors of the index of Cullen Numbers seems to be a reasonable approach. Consider the case where two consecutive Cullen Numbers are divisible by the same prime divisor. These comprise about 80-90% of all Cullen Numbers in the range of indexes of 102 - 103 and about 50-65% of all Cullen Numbers in the range of indexes of 107 - 108. A brief survey of the Cullen Numbers from C900 to C1000 reveals that a full 80% of those Cullen Numbers are found to be divisible, in pairs, by the same prime factor. Just under 30% of these are the two Cullen Numbers preceding a prime index. There are an equal number of pairs due to a shared prime divisor that is found in the factorization of a Cullen Number index immediately following the pair, where the factorization was comprised of two distinct factors or one distinct factor squared. The remaining 20% are pairs of Cullen Numbers sharing prime divisors that are found in the factorizations of a Cullen Number index immediately following the pair, where the factorization was comprised of more than two factors. This information was derived from the Cullen Number factorizations available at Paul Leyland's website (link is at the bottom of this page). The 20 Cullen Numbers from C900 to C1000 that had no factors revealed in pairs can be reduced to just eight by sieving for primes less than 1000. Further sieving would achieve no significant results untill we reached six to eight digit primes in trial division, leaving just C915, C933, and C941 as divisible by only very large primes. The smallest of these is 197724478669, which is a twelve digit prime factor of C933. Interestingly, C933 has only one other factor and that is a prime number with 273 decimal digits.

We begin with the simple case where an index n of a Cullen Number cannot be factored at all. In this case we will say that n = p. It is a simple matter to show that the congruencies Cn-1 mod p and Cn-2 mod p result in the congruency -2p-1+1 mod p, which is of course, due to Fermat, zero mod p. This proves the basic divisibility property that if n is prime then Cn-1 and Cn-2 are divisible by n=p and so cannot themselves be prime.

We go one step further and suppose that n = p.p so that n has two factors, both equal and both prime. We again substitute and solve the congruencies for Cn-1 mod p and Cn-2 mod p and find that, in either case, -2pp-1 + 1 mod p results in zero mod p. This result was obtained as before by exponent reduction and the proof of Fermat. This proof can be extended for any power of a prime p.

Using the examples above as a guide, we suppose that n = p1 . p2 so that n has two distinct prime factors. We further suppose that p1 is less than p2. We will now explore the cases where n is not prime but Cn-1 and Cn-2 are divisible by one of the prime factors of n. Some examples of such cases: C339 and C340 are both divisible by 11 and 31. The number 341 factors as 11 . 31; C669 and C670 are both divisible by 11. The number 671 factors as 11 . 61; C831 and C832 are both divisible by 17. The number 833 factors as 72 . 17, which is a slightly different case.

This page is in progress - April 14, 2010



Links to Visit for Further Information on Cullen Numbers





URL: http://members.bex.net/jtcullen515/math1.htm
© Oct, Nov 2005 - James Cullen - all rights reserved.

Use your Back Button or click here to go to the Math Index