[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

501.0. "Big prime number." by SANFAN::WOODRI (Interdum Vincit Bozo) Thu Jun 05 1986 01:45

This might be more appropriate to programmers, but alas:

Illustrate, using some type of psuedo-language, the algorithm for the 
quickest method for finding the first ten-digit integer that contains 
all ten digits and is prime.  Bonus points for innovativeness.

T.R	Title	User	Personal Name	Date	Lines
501.1		CLT::GILBERT	Juggler of Noterdom	`Thu Jun 05 1986 02:27`	6
	Spoiler: Any ten-digit number that contains all ten digits must be a multiple of 9, by 'casting out nines' (the sum of the digits in this number is 45). Thus, there is no ten-digit prime that contains all ten digits.
501.2		CLT::GILBERT	Juggler of Noterdom	`Thu Jun 05 1986 04:47`	34
	Alright, what's the smallest prime that contains all ten digits? Spoiler follows: The smallest integer that contains all ten digits and is not a multiple of 9 is 10123456789 (i.e., the 'doubled' digit cannot be a 0, since we'd have the 'casting out nines' argument again). This, and the next smallest such numbers are given below, along with their factorizations (thanks to Hallyburton's FACTOR program): 10123456789 = 919 * 11015731 10123456798 = 2 * 7 * 13 * 97 * 573437 10123456879 = 21521 * 470399 10123456897 = 281 * 36026537 10123456978 = 2 * 3433 * 1474433 10123456987 = 7 * 7 * 9833 * 21011 10123457689 = 10123457689 10123457698 = 2 * 15601 * 324449 10123457869 = 7 * 7 * 733 * 281857 10123457896 = 2 * 2 * 2 * 757 * 1671641 10123457968 = 2 * 2 * 2 * 2 * 13 * 151 * 157 * 2053 10123457986 = 2 * 5061728993 Thus, we've easily found the smallest such prime, namely, 10123456789 with the '6' and '7' swapped. Although I used the FACTOR program to produce the above list, I'd originally written a small program that cycled through permutations of the ten digits, added 10000000000, then tested for primality by trial divisors (using a pre-built table of all primes < 65536). I hadn't expected it to discover a prime so soon.