Second smallest integer with 100 divisors??

Discussion in 'General Math' started by don.lotto, Sep 18, 2008.

1. don.lottoGuest

puzzle.. Second smallest integer with 100 divisors??

don s. mcdonald. +64- 4 xxx wellington nz.
18/9/08.

don.lotto, Sep 18, 2008

2. kenGuest

102!/101

ken, Sep 18, 2008

Don McDonald posts a legible puzzle for once:
Ken Johvi tries:
Hardly! That number equals

2^98*3^49*5^24*7^16*11^9*13^7*17^6*19^5*23^4*29^3*31^3*37^2*41^2
*43^2*47^2*53^1*59^1*61^1*67^1*71^1*73^1*79^1*83^1*89^1*97^1

[where * is multiplication and ^ is exponentiation]

and therefore has

99*50*25*17*10*8*7*6*5*4*4*3*3*3*3*2*2*2*2*2*2*2*2*2*2
= 46,903,836,672,000,000

divisors. You just add 1 to each exponent in the prime factorization
and multiply them together. (Then subtract 2 if you want proper divisors,

As far as I can see the 5 smallest numbers with 100 divisors are:

475,368,975,085,586,025,561,263,702,016 = 2^97*3^1
594,211,218,856,982,531,951,579,627,520 = 2^95*3^1*5^1
633,825,300,114,114,700,748,351,602,688 = 2^99
713,053,462,628,379,038,341,895,553,024 = 2^96*3^2
792,281,625,142,643,375,935,439,503,360 = 2^97*5^1

We don't need to consider numbers with larger prime factors because
2^2 < p^1 for prime p > 3.

4. Simon TathamGuest

Does that not therefore have 98*2 = 196 divisors? You appear to have
added one to each exponent and then _summed_ rather than multiplying.

Simon Tatham, Sep 18, 2008
5. Simon TathamGuest

As far as I can see, the possible factorisations of 100 are 2.2.5.5,
4.5.5, 2.5.10, 2.2.25, 2.50, 5.20, 4.25, 10.10, 100. Hence any
number with exactly 100 divisors must be of one of the following
forms, for some distinct p,q,r,s:

- p q r^4 s^4
- p^3 q^4 r^4
- p q^4 r^9
- p q r^24
- p q^49
- p^4 q^19
- p^3 q^24
- p^9 q^9
- p^99.

The smallest number of each of these forms is obtained by raising
the smallest prime to the largest power, so in each case we have

- 7.5.3^4.2^4 = 45360
- 5^3.3^4.2^4 = 162000
- 5.3^4.2^9 = 207360
- 5.3.2^24 = 251658240
- 3.2^49 = 1688849860263936
- 3^4.2^19 = 42467328
- 3^3.2^24 = 452984832
- 3^9.2^9 = 10077696
- 2^99 = 633825300114114700748351602688

Of these, the smallest is 45360. The second smallest is therefore
either one of the others, or the second smallest number of the form
p q r^4 s^4. That second smallest number is obtained by substituting
the next prime (11) for the 7, giving 11.5.3^4.2^4 = 71280, which is
still smaller than any of the rest of the numbers in the above list.
Hence 71280 is the second smallest number with exactly 100 divisors.

Simon Tatham, Sep 18, 2008
6. Phil CarmodyGuest

Surely a number with 105 divisors (say) also has 100 divisors?
(All months have 28 days...) I don't think it changes the answer,
though (as 129600 is the smallest with such a profile).
You do explicitly insert the "exactly" in that sentence. Do you think

Phil

Phil Carmody, Sep 18, 2008
7. Simon TathamGuest

It's certainly possible; that's why, in the absence of clarification
explicitly which of the possible questions I was answering.

A computer search suggests that the answer is indeed different if
you want the second smallest number with _at least_ 100 divisors;
but I haven't (yet) thought of a particularly nice proof that
derives the answer without excessive tedious brute force searching.

Simon Tatham, Sep 18, 2008

Well, it was close enough for government work.

9. don.lottoGuest

What is the smallest positive integer with exactly 360 divisors ?

and so on. hardy highly composite numbers.

on the first puzzle, I was thinking 10^9. but it isn't the 2nd
smallest.

I have done lots of research on these problems sci.math. )

Don S. McDonald, Wellington 19/9/08.

don.lotto, Sep 19, 2008
10. CBFalconerGuest

Well, to me the divisors of 12 are as follows:

12 = 1 * 12 2 divisors
= 1 * 3 * 4 2 more divisors
= 1 * 3 * 2 * 2 2 more divisors
HAH 6 divisors total.

Remove the 1, and you get 5 divisors. The removal allows
calculation from the divisors of factors.

CBFalconer, Sep 19, 2008
11. MensanatorGuest

3603600?

Whose divisors are

1
2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 18 20 21 22 24
25 26 28 30 33 35 36 39 40 42
44 45 18480 50 52 55 56 69300 60 63
65 66 70 72 75 77 78 80 84 88
90 91 2145 99 100 104 105 110 112 3432
117 120 126 130 132 2184 140 143 144 150
2200 154 156 165 168 175 176 180 182 4290
195 198 200 3603600 208 1400 210 220 225 2275
231 234 240 252 260 2310 264 4368 273 275
51480 286 3120 6435 2340 300 4400 308 12600 2100
315 325 330 336 10296 350 360 364 385 8580
390 72072 396 400 6552 514800 420 2475 429 440
25025 450 4550 455 6600 462 468 2520 30800 10725
495 504 520 4620 525 2574 528 600600 546 550
2600 80080 560 572 12870 4680 585 2640 600 616
624 4200 630 150150 650 109200 660 60060 20592 27300
6160 15015 10920 6825 2730 39600 693 700 400400 715
6864 46200 2772 728 2800 770 17160 780 144144 6930
792 2860 13104 9009 819 825 840 11088 4950 858
64350 55440 23400 2925 880 50050 900 9100 5005 910
13200 924 936 6300 17325 48048 3003 21450 975 990
720720 1001 7150 1008 3080 1040 9240 1050 5148 1200
15400 1201200 25200 1092 27720 1100 3150 5200 3600 40040
7280 1144 720 1155 25740 9360 1170 11440 36036 3276
1232 8400 3300 1260 15600 1287 300300 1300 11550 1584
1320 120120 75075 54600 30030 21840 13650 5460 1365 19800
138600 23100 1386 257400 3465 1430 2288 48 5544 32175
1456 11700 24024 3575 1540 200200 34320 7700 1560 5040
13860 1575 36400 20020 102960 3640 277200 1801800 171600 5720
18018 1638 3696 1650 7800 5775 16016 280 240240 9900
1716 128700 46800 5850 12012 7920 100100 1800 3850 18200
10010 1820 900900 85800 1848 3900 8008 1872 312 34650
1680 92400 57200 6006 3960 1925 450450 42900 1950 4004
360360 327600 28600 1980 225225 2002 180180 163800 14300 90090
81900 65520 45045 40950 32760 20475 16380 8190 4095

Mensanator, Sep 19, 2008
12. Phil CarmodyGuest

Where's '6' hiding?
No idea what that means.

The number of divisors is the product of 1 more than each of
the exponents in the prime factorisation. There's no other
sensible way to approach it that doesn't end up being more
complicated than that for anything with more than a handful
of factors.

Curiously, this means that you don't always need to know
the prime factorisation in order to know the number of
divisors in a few corner cases.

Phil

Phil Carmody, Sep 19, 2008
13. CBFalconerGuest

I goofed.
I wanted to arrange something that would allow finding the factors

CBFalconer, Sep 19, 2008
14. don.lottoGuest

Search: id:A037025

Displaying 1-1 of 1 results found. page 1

Format: long | short | internal | text Sort: relevance |
references | number Highlight: on | off

A037025 a(n+1) = least k with d(k) = a(n). +0
3

8, 24, 360, 3603600, 2549066103582535692163008000000 (list; graph;
listen)

OFFSET 1,1

CROSSREFS Cf. A000005, A009287.

Adjacent sequences: A037022 A037023 A037024 this_sequence A037026
A037027 A037028

Sequence in context: A094061 A002268 A050893 this_sequence A103624
A105063 A132586

KEYWORD nonn,nice

AUTHOR Don McDonald (dsmcdona(AT)actrix.gen.nz) ??
don s. mcdonald whitepages.co.nz wellington new zealand.

EXTENSIONS One more term from Naohiro Nomoto
(6284968128(AT)geocities.co.jp), Jun 28 2001

thanks, well done!

don, i'll give recursive factorisations in a moment ??
don, i'll give recursive factorisations in a moment ?? ////////////

don.lotto, Sep 20, 2008
15. don.lottoGuest

On Sep 20, 11:52 am, wrote:

19.04.04 00:40. SENT.
21.04.04 00:27 edited

an.societ.Science.Mathematic.NZMM.prim+fact
an.societ.Science.Mathematic.NZMM.SPRIMFACT > THIS FILE.

NZMM New Zealand Mathematics Magazine.

Math Mag Article submission 2,Primes and factors.
Primes and factors. (Second draft..)******************
===============**

Introduction.
New Zealand car license plates issued in year 2000 often
had 4 or 5 digits and possibly a letter or two.
Glancing at plates of parked cars on my walks
frequently inspired observations of the personalities
of numbers up to 9,999.

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.
My biggest breakthrough followed after a Wellington
newspaper article reported in 6 Aug. 1989 that the World's
largest known prime number then was 391 581x 2^ 216193 -1.
On 17.8.1991 I advertised (Evening Post)
that 7, 6199, and 92219, etc., divide 4W+3.

I set out to find factors of numbers represented as
c*a^b+n. (Program PrimeCabi.)
You should readily be able to verify that the huge number,
given above in multiple-exponent form, is 1 less than an
exact multiple of 6.

Readers' Guide Abstracts CD_ROM reviewed a later Mersenne
prime discovery, saying 2^858 433-1 is prime.
Actually it isn't! A theorem says any divisor of 2^prime-1
(must be?) of the form 2kp+1.

(The correct exponent should have been 859,433.
That is: figure 9 instead of 8.)

A program to calculate prime numbers.

100PRINT "BASIC V PROG PRIMESQP+2, (SHORT + SIMPLE)"
110 PRINT "BY DON S. MCDONALD, 18.4.04"
Page 1
110INPUT "COUNT PRIMES UP TO N. ENTER N";N
120PRINT N : C = 2
130PRINT "PRIMES: 2, 3, ";
140FOR P = 5 TO N STEP 2
150FOR Q = 3 TO SQR P STEP 2
160 IF P MOD Q = 0 THEN Q = P
170 NEXT Q
180 IF Q <> P+2 THEN C += 1: PRINT ;P", ";
190 : IF POS > 33 THEN PRINT
190 NEXT P
200
210PRINT' "NUMBER OF PRIMES UP TO ";N " = ";C
220PRINT "CONTINUE OR <ESCAPE>.";GET\$ : RUN

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.

Mersenne numbers.
Although Mersenne numbers are 'binary palindrome repunits,'
2^prime-1, I have noted some exponents may be a member of a
twin prime, and the one time record holder exponent
3021 377 equals 1*2*34*44432+1. The digits increase by 1,
plateau at '4', and then descend by 1s. I call it
'palindrome Table Mountain', no less! //TTT\\\..
And I will always remember it longer.

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.
I also obtained a Toshiba 486 Windows-1995 laptop computer.
A month later I proposed (groups.google.com, sci.math)
"IsPrime(billion ^ billion +3)?", (Bb+3.)

: Date: Thu, 25 Nov 1999 12:02:41 -0700 (MST)
: From: Kurt Foster <>
: To: Don McDonald <>
: Subject: Re: Isprime (billion to billion plus 3.)?
:
: I'll call 10^(9*10^9) "bb" in what follows. Let's see: working
with
: pencil and paper, I resolved bb+1 as a product of about 300 proper
: factors. You found a couple of small prime factors of these.
: You found a small prime factor of bb+3.
:
: don. 1.58+ billion

However, the fourth to last entry in 'Penguin dictionary of
curious and interesting numbers' (David Wells, Revised edn
1997) is gigaplex. It is supposed to be a huge number but
the book just says
"1^billion (? sic), 1 with a billion zeroes."

My 'Bb+3' number is larger than Gigaplex
and in fact mathematician Bob
Silverman believed it was not feasible to test by Fermat's
Little Theorem.
A week later - and 96 hours of computer time, I confirmed
1580,187,223 divides (10^9)^(10^9)+3. Perhaps its least
prime factor.

A dozen math posters eventually were persuaded and checked
my work with Derive5, etc. UBASIC32 is the number theory
programming program for MS-Dos.

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.
There may be an advanced book called 'Primality testing and
computer methods of factorisation.' (Riesel?) However, all my
programs use Basic2, Basic-V, or BBC Basic64.

The largest integer in BASIC (Beginners' All-purpose
Symbolic Instruction Code) is 2^31 -1, equals approximately
2.147x10^9. (My family birthdate.)

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 DIV 2 = 0 THEN PRINT"multiple of 2":STOP
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

The MOD operation above gives the remainder when INTEGER n
is divided by INTEGER x.
Unfortunately, it quickly runs into trouble after that.
PRINT (2^31) MOD 2 will not work because n exceeds the
integer limit.

I did a work around for integers up to 2^52 = 4.5x10^15,
which I call "phone numbers, birthdates, lotto combinations,
and creditcard numbers." My experiments showed BASIC64
REAL arithmetic with integers is exact
up to this much higher limit.

For example,
IF x*INT(n/x)=n THEN PRINT "factors" x "*" n/x

continues to work up till 2* (2^31-1); only a minor
reprieve.

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.)

If hcf (or greatest common divisor) is greater than 1 (by
its prime factorisation, which includes factors of n.

Hcf(n,x) with primorials does not have the same risk of
integer overflow that we had with small divisors
INT ((2^32)/2). Several
prime factors may be tested with one primorial.

(There may be a so-called 'continued fraction method' of
factorisation.)

I deflate n by x and try again, eventually trying
pre-calculated primorials, or runs of primes, up to
(2*30030)^2.
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 c241 can convert words to numbers: Option t.
Alpha characters are replaced by touchtone telephone keypad
numeric equivalents.

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

Interesting numbers.

"red yellow"** telephone keypad and base 27?
Both are prime, below. (Query primary colours.)

"spectrum"** base 100. Has large factors by programs
pari-gp, IsPriMe2kp. (below.)

(factor phone nums, birthdates, credit card numbers.
by don.mcdonald.pgm.c241Q.

== LETTER values : *counting letters*
C,A,T = 03,01,20. B,A,C,H = 02,01,03,08. (BASE 100, Alternate base
27,
telephone keypad*** numeric equivalent on touch tone telephone

(prob) -- #formula,-- value, -- FACTORS -- , (centiseconds).
---
11) "red yellow"(teleph kp..=733935569= 733935569*all 1s.
***
12) "red yellow"(base 27..=5137944729881= 5137944729881prime 3mn
***

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.********

multiplier * (base ^ index) + offset <= neighbourhood.
2E9 2E9 2E9 2E9 2^5.

find factors p, satisfying , Sint = spectrum base 100
ABS( 19160503 * 100 ^ 4 + 20182113
....