# The factorising game or industry can escalate from trivial to extremely difficult

Discussion in 'NZ Computing' started by don.lotto@paradise.net.nz, Jan 13, 2007.

1. ### Guest

(Don McDonald) wrote in message
<news:>...
> 21.04.04 00:27 edited

> Primes and factors. (Second draft..)******************
> ===============**

bbc basic-V programs now at nz.test. tSeriCalc TEXTc241Q.
Acorn RISC OS 3.11 25KB etc.
22.4.04
.... snipped throughout.

> Introduction.
> For the last 35 years I have regularly created programs for
> calculating primes and factors. Example, the lottery pool
> should be a multiple of 28 cents or similar.

> The factorising game or industry can escalate from trivial
> to extremely difficult.

> Primality testing.

> I set out to find factors of numbers represented as
> c*a^b+n. (Program PrimeCabi.)
> A program to calculate prime numbers.

> Pari-gp.

> Pari-gp is a remarkable number theory/research calculator
> that I received on floppy diskette for Acorn RISC_OS
> computers. You may wish to compare your results with
> hundreds of number theory functions on pari-gp, including
> primes(), nextprime() , isprime(), smallfact(), and
> factor(), numdiv(), divisors().

> My own program, SeriCalc4S, has over 40 functions.

> Factors.
> Program 'Factors' accepts an integer or expression as input
> and prints out the prime factorisations of integers
> starting there, with an optional step of 1, 6, or 1-00-00
> (date dd mm yy), whatever etc. I always like to *spool my
> interactive sessions to a text file, including everything
> that I type into the computer and the complete results
> displayed.

> How can you do that on MS-DOS?

> My other programs sometimes give only the least prime
> factor of each integer, the least squared prime factor, the
> next prime, Sophie Germain primes,
> or all twin primes in a large block of integers.

> SeriCalc4S.
> My program SeriCalc4S (serious-serial number theory
> scientific statistics printout calculator) offers functions
> least prime factor (* co-factor) or divisors. It reports
> Page 2
> associated data - whether abundant, deficient, prime,
> perfect or square, etc. It began life as my 1-line
> calculator. ***

> 16*KEY8INPUT R:REP.:I.SPC4; A\$:
> A\$=STR\$(R)+A\$:R=EVAL(A\$)RINT"= ";R;:U.FA.|M

> UBASIC.
> On-line Encyclopedia of Integer sequences gives sequence
> EXTENDED A076670
> for divisors of 'Bb+1'= (10^9)^(10^9)+1. I advertised
> these also in NZ Science Monthly bulletin board, April- May
> 2000(?). Please verify divisor 864,ooo,oo1. I call this
> "number of seconds in 10,ooo days plus a heartbeat (a short

> Facthcf, c241Q. source at nz.test. TEXTc241Q.

> I have an Acorn A5000 computer (UK 1990) with 4 MB RAM and
> 345 MB IDE HDD (hard disk drive.) It has been extremely
> reliable, despite its lowly specification. Megabytes
> random-access memory.

> The simplest trial division program shows 2^31-1 is prime
> in 6 seconds. Any Basic integer should be factored in this
> time or less.

> IF n MOD 2 = 0 THEN PRINT"multiple of 2":STOP

fixed
> FOR x = 3 TO SQRn STEP 2
> IF n MOD x = 0 TH. PRINT "factors"; n "=" x "*"n/x": STOP
> NEXT x
> PRINT n "is prime"
> Page 3

> My second breakthrough is the Euclidean algorithm.

> I calculate primorial 23, namely the product of all primes
> up to 23. I find x= a multiple of primorial 23 that is
> nearly 2^31. I then find highest common factor of (n,x.)

> Problems (85-92.)

> 85) R%(prob-83)..=2007835830= 2*3*3*3*5*7*11*13*17*19*23*all 7cs
> 86) R%(prob-83)..=2111136084= 2^2*3*3*29*31*37*41*43*all 7cs
> 87) R%(prob-83)..=1801986909= 3*47*53*59*61*67*all 7cs

> 92) R%(prob-83)..=1935984741= 3*151*157*163*167*all 8cs

> 2) 60037*60041^2 ? example..=216428682962197= 60037*60041*60041*all
> 10s.

> Program c241Q may resolve all numbers not exceeding
> semi-primes 6E4*2^31, and larger numbers with 2 or more
> integer factors.

> Page 4
> Extra features.
> n= last factor, n1= last test, P%()=primes, R%()=primorials
> R.r generate random candidate number
> p() = previous results, prob=PROB= array index,
> return=repeat expression.
> * summary results.

> Program c241Q can convert words to numbers: Option t.
> Alpha characters are replaced by touchtone telephone keypad
> numeric equivalents.

> Program c241Q can also represent words by (base 100) integers
> (H=,08,) or (base 27) integers,
> "BC" ==> 2*27+3.
> Options c and z.

> Interesting numbers.
> "spectrum"** base 100. Has large factors by programs
> pari-gp, IsPriMe2kp. (below.)
> Pari-gp.
> ? "spectrum"( base 100)

> ? factor(19,16,05,03,20,18,21,13)
> %3 =
> |6419989 1 |

> |298450717 1 |
> *********************
> 6.4 mill x 298 mill. yes.********

> find factors p, satisfying , Sint = spectrum base 100
> ABS( 19160503 * 100 ^ 4 + 20182113 ) <= 0 MOD p.

> Here's a numeric curiosity concerning word "Environment", etc.

> (problem/) -- #formula,-- value, -- FACTORS -- , (centiseconds).
> ---

> 31) "environment"(numeric equivalent on telephone keypad..

> =36847666368= 2^3*3*3*3*2^3***21323881*all 36cs
> curiously contains factor 12 cubed.

> 35 "c,u,b,i,c"(base 100.. = contains factor 7^4th. (raised to a
> power.)
> =3,21,02,09,03= 7*7*7*7***19*31*227*all 6cs
> contains factor 7^4.
> > ?sedna planet

> s/ 19 th letter 19 base 27
> e/ 5 th letter 518 base 27
> d/ 4 th letter 13990 base 27
> n/ 14 th letter 377744 base 27
> a/ 1 th letter 10199089 base 27

> p/ 16 th letter 275375419 base 27
> l/ 12 th letter 7435136325 base 27
> a/ 1 th letter 200748680776 base 27
> n/ 14 th letter 5420214380966 base 27
> e/ 5 th letter 146345788286087 base 27
> t/ 20 th letter 3951336283724369 base 27

> "sedna planet"(base 27 = 3.951E15 ****
> "sedna planet"(base 27 = 3951336283724369 ****

> >>9) "sedna planet"(base 27..=3951336283724369= ? 37s.

> I gave up abandoned the program after 5 minutes on previous run
> and cracked it much (quicker) with Fermat method.
> (Square minus a square.)

> 65.2 mill x 60.6 mill ??

> "sedna planet" (base 27.)
> extremely lucky. factorised in about 1 minute.
> as follows..

> Fermat factor method, don.mcdonald, 6.3.04, 10 pm.
> Pgm, bignum.FermatMeth.FactMethod. BASIC64? may be VERY slowx.

> ENTER numeric expression res\$, 1E12+3, sedna, (2E5+3)*1003 (2min.)
> xa, xb, Rr= GENERATE , <1 quit. ?sedna
> "Sedna Planet"(Base 27.)
> Factor 3951336283724369 = 3.95133628E15
> cubert = 158093.737, 2/3-rt.= 2.49936295E10, sqrt=62859655.5
> ,,,
> xa * xb= (62901975^2 - 2306984^2)
> =65208959*60594991 factors <ESC> 62.05 s.
> xa * xb= 65208959*60594991 factors <ESC>

> END. *spool *RAM.spFerMeth *** TREMENDOUS ************

don.lotto mcdonald
repost 13-1-07.

, Jan 13, 2007