Second smallest integer with 100 divisors??

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

  1. don.lotto

    don.lotto Guest

    puzzle.. Second smallest integer with 100 divisors??

    don s. mcdonald. +64- 4 xxx wellington nz.
    18/9/08.
     
    don.lotto, Sep 18, 2008
    #1
    1. Advertisements

  2. don.lotto

    ken Guest

    102!/101
     
    ken, Sep 18, 2008
    #2
    1. Advertisements

  3. don.lotto

    Mark Brader Guest

    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,
    but that's not what we weren't asked about.)


    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.

    So the answer is 594,211,218,856,982,531,951,579,627,520.
     
    Mark Brader, Sep 18, 2008
    #3
  4. don.lotto

    Simon Tatham Guest

    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
    #4
  5. don.lotto

    Simon Tatham Guest

    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
    #5
  6. don.lotto

    Phil Carmody Guest

    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
    you're answering a different question from that which Don asked?

    Phil
     
    Phil Carmody, Sep 18, 2008
    #6
  7. don.lotto

    Simon Tatham Guest

    It's certainly possible; that's why, in the absence of clarification
    about which question he meant to ask, I made sure to state
    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
    #7
  8. don.lotto

    Mark Brader Guest

    Well, it was close enough for government work. :)
     
    Mark Brader, Sep 18, 2008
    #8
  9. don.lotto

    don.lotto Guest

    What is the smallest positive integer with exactly 360 divisors ?

    and so on. hardy highly composite numbers.
    the answer is affirming. CHECKED.

    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
    #9
  10. don.lotto

    CBFalconer Guest

    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
    #10
  11. don.lotto

    Mensanator Guest

    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
    #11
  12. don.lotto

    Phil Carmody Guest

    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
    #12
  13. don.lotto

    CBFalconer Guest

    I goofed.
    I wanted to arrange something that would allow finding the factors
    and adding the divisors those factors had. Oh well.
     
    CBFalconer, Sep 19, 2008
    #13
  14. don.lotto

    don.lotto Guest

    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
    #14
  15. don.lotto

    don.lotto Guest

    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$):pRINT"= ";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
    lifetime.)"


    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
    hypothesis it is less than 2^31,) we have ready access to
    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.


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


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

    read more »

    Don S. McDonald, Wellington 19/9/08.- Hide quoted text -
     
    don.lotto, Sep 20, 2008
    #15
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.