PRIMES, SEMI–PRIMES, AND STRONG COMPOSITES

Richard L. Francis

Southeast Missouri State University

As is well known, all integers greater than 1 are either prime or composite. In particular, a composite number of two or more digits will be called a semi–prime if it can be transformed into a prime simply by changing its first digit. A leading digit of 0 (zero) will be considered unacceptable in the transforming process. Hence, the composite number 27 is a semi–prime as the changing of its first digit from 2 to 1 results in the prime number 17. The finding of examples of semi–primes is a fairly simple task. However, deciding the cardinality of such a set is another matter. Before answering the cardinality question, several explorations among the integers should be pursued. We will begin by noting that a prime number to which a semi–prime is transformed is called a metamorphic prime. For example:

A Corresponding

Semi–Prime Metamorphic Prime Not a Semi–Prime
33  23  37
157  257  56
9999  1999  125
75537  65537  21478015854767451
116091  216091  53798277528181133

An example of a number which is not a semi–prime is 56 (as shown in the table above). No even number or a number with a last digit of 5 can be a semi–prime as factorization is always guaranteed regardless of the first digit choice. Actually, all primes of two or more digits are metamorphic. That is, it is always possible by an alteration of the prime’s first digit to obtain a mutiple of 3. Infinitude of the Semi–Primes

The fact that the set of primes is infinite and moreover, that the set of metamorphic primes is resultingly infinite, permits a quick disposition of the cardinality question in reference to the semi– primes. All primes of two or more digits are of the form 3n + 1 or 3n + 2. Should a prime be of the form 3n + 1, simply decrease its first digit by 1 or increase it by 2 so as to form a multiple of 3. The resulting composite number will of course be a semi– prime. Actually, the coinciding of semi–primes in this approach must be considered. For example, both 13 and 43 are associated with the semi–prime 33. As several primes can be associated with a single semi–prime, some caution in counting must be exercised. In particular, suppose a select prime of the form 3n + 1 has k digits. Then at least one semi–prime can be found having k digits by transforming the prime into a multiple of 3 (as shown above). Yet a prime of the form 3n + 1 with a greater number of digits, say L digits, can be formed so as to generate a semi–prime of L digits. Noting that the number of digits can be made larger than any assigned number guarantees the infinitude of the set of semi– primes.

Consider, for example, the large prime given by

86,759,222,313,428,390,812,218, 077,095,850,708,048,977.

This prime is of the form 3n + 1 which means that the sum of its digits is 1 more than a multiple of 3. Should the first digit (an 8) be changed to a 7, the number will become a multiple of 3. Such a composite number is accordingly a semi–prime.

Still another example is given by the enormous prime

108,488,104,853,637,470,612,961,399,842, 972,948,409,834,611,525,790,577,216,753.

As this prime is also of the form 3n + 1, increasing its first digit by 2 will result in a multiple of 3. Note that the changing of the first digit to a 0 (zero) is not an allowable transformation.

A semi–prime can be found for any number of digits other than 1. This can be proved by showing that infinitely many primes have an initial digit of 1 (such as 19, 103, and 1933). By Bertrand’s Theorem, a prime exists between any number greater than 1 and its double. Hence, between 1(10)^{n} and 2(10)^{n}, there exists at least one prime for all n greater than zero. Such a prime clearly contains (n + 1) digits. It follows that there are infinitely many primes beginning with 1; moreover, these primes can be chosen so as to have any desired number of digits (other than 1).

Consider now any prime with a first digit of 1 and having a preferred number of digits. As before, the leading digit 1 can be changed so as to form a multiple of 3. In this case, a composite number (a semi–prime) is formed having the same number of digits as the prime itself. The sixty digit prime shown above is a prime with a leading digit of 1. Changing this first digit to a 3 results accordingly in a sixty digit semi–prime.

308,488,104,853,637,470,612,961,399,842, 972,948,409,834,611,525,790,577,216,753 A Sixty Digit Semi–Prime

As noted, it is easy to form semi–primes once prime numbers are given. However, primes are not always so easily exhibited. Although the set of primes is infinite, the largest \underline{known} prime is 2^{216091} − 1, a number of 65,050 digits. Hence, a limitation is semi– prime construction is to be stressed. The proof of the infinitude of the set of semi–primes is existential; it does not permit an actual exhibition of arbitrarily large semi–primes. Nor should it be concluded that all odd composites not ending in 5 are semi–primes. Otherwise, semi–primes would be easily generated. To stress this fact, another number classification is needed. Strong Composite Numbers

An odd composite number not ending in 5 and which is not a semi–prime will be labeled a \underline{strong composite}. To show that the set of strong composites is not the empty set, consider the following construction:

Let x be the product (11) (21) (31) (41) (51) (61) (71) (81) (91), that is, 478015854767451. Prefixing this particular digital sequence (called the suffix) with 11 yields y_{1}, namely

11478015854767451.

As 11 divides itself (the prefix) as well as the suffix, it also divides y_{1}. Should the 1 be changed to 2, the prefix becomes 21 which divides itself and the suffix. Hence, 21 divides the entire number, say y_{2}. More generally, for any choice of the leading digit, and due to the manner of constructing the suffix, composite numbers result each time. Accordingly, 11478015854767451 does not become prime for any selection of initial digits. It is an example of a strong composite number.

If in this example, the suffix is now repeated, a still larger strong composite number is formed. Repetition can of course be performed as many times as desired. This implies the infinitude of the set of strong composite numbers. One may also wish to build on the product (13)(23)(33)(43)(53)(63)(73)(83)(93), that is, 798277528181133, to suggest still another infinite subset of the set of strong composite numbers. Orders of Semi–Primes

Suppose that greater freedom exists in the case for changing composites to primes. In particular, suppose one may change the first two digits (of a number of three or more digits) in the attempt to form prime numbers. Note for example the prime 21701 which is of the form 9n + 2. Should the first two digits be changed so as to form 64701, a multiple of 9 results. Actually, any prime of two or more digits can be associated with a composite number by an alteration of its first two digits to form a number divisible by 9. These resulting composite numbers will constitute an infinite set as the set of primes is itself infinite. Moreover, they will be labeled semi–primes of order two. An example is the number 64701 above. The concept is easily generalized to semi–primes of any order.

Consider also any odd composite number which does not end in 5 and has three or more digits. Suppose it is further stipulated that composite numbers must result no matter how the first \underline{two} digits are changed. Such resulting numbers will be called strong composites of order two. To find an example, first form the product (say z) which equals (101)(111)(121) ⋯ (191)(201)(211) ⋯ (901)(911)(921)(931) ⋯ (991). Place, for example, 101 in front of the z sequence of digits in constructing the digital representation of a number. No matter how the first two digits are changed in this gargantuan number, composites result. Should the first two digits be changed to 37, then 371 will divide not only the prefix (371) but the suffix (z) also. Such a technique produces a strong composite of order two. Repetition of the suffix gives rise to still larger composites of this order and implies the infinitude of the set. The process of constructing strong composites of order two can be generalized to strong composites of any order. Changing All Digits

Does there exist a number so that only composites result even if all its digits are changed? The answer is “no.” Consider a composite number of exactly m digits. As shown earlier, there exists a prime of m digits no matter what the designated value of m. Hence, a prime can always be obtained from any composite number by an allowable alteration of all its digits. Explorations

Various explorations stem from the discussion above. Such explorations include the following:

1. What is the least semi–prime?

2. What is the largest semi–prime less than 1000?

3. What is the least strong composite?

4. Account for the development of semi–primes in base three arithmetic. Why must binary arithmetic be excluded from

a generalized treatment of semi-primes?

5. A composite number of two or more digits which can be transformed into a prime by changing its last digit is “nearly prime.” Show that the set of near primes is infinite.

6. Find a composite number which does not transform into a prime regardless of its last digit alteration. Are there infinitely many composites in this category?

7. Is it possible for a repunit number, that is, a number consisting of ones in its representation, to be a strong composite?

8. Show that there are infinitely many primes with a first digit of 2 or 3. Show that there are infinitely many primes with a last digit of 2 or 3.

9. Is the set of semi–primes closed with respect to multiplication?

10. An absolute prime is a number which is prime regardless of the arrangement of its digits (such as 991). Find seven examples of an absolute prime. Note: It can be shown that no absolute prime exists which contains all of the digits 1, 3, 7, and 9.

Fascination with the primes seems to be a trait or mark of every generation, be it that of Eratosthenes in the ancient world or a host of mathematicians in the moden setting. Variations on the prime number concept have opened doors to promising fields of exploration also. These include such composite numbers as those called pseudo–primes, Carmichael numbers, and more. Somewhere in this varied look are found the semi–primes, a fascinating class of numbers which, by only an initial or leading digit, miss the mark of primality.

\underline{References}

1. A. H. Beiler, \underline{Recreations in the Theory of Numbers : The} \underline{Queen of Mathematics Entertains}, Dover Publications, New York, 1964.

2. T. N. Bhargava and P. H. Doyle, “On the Existence of Absolute

Primes,” Mathematics Magazine 47 (September 1974), 233.

3. R. L. Francis, “Mathematical Haystacks: Another Look at Repunit Numbers,” The College Mathematics Journal 19 (May 1988), 240–246.

4. M. L. Gardner, “The Remarkable Lore of the Prime Numbers,” Readings from Scientific American, W. H. Freeman and Co., San Francisco, 1978.

5. K. H. Rosen, Elementary Number Theory and Its Applications, Addison–Wesley, Reading, 1988.

11