?
Solved

Number Question

Posted on 2003-02-19
16
Medium Priority
?
591 Views
Last Modified: 2008-02-01
heres one I've had passed on to me, apparently a competition in 'New Scientist' magazine

48 is the lowest mumber with 10 factors (inc 1 and itself) i.e. 1,2,3,4,6,8,12,16,24,48

similarly to above,

1) what is the lowest + number with exactly 1,000 factors

2) how many prime factors does the first number to have 100,000,000 factors have
0
Comment
Question by:deighton
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 5
  • 2
  • +2
16 Comments
 
LVL 22

Expert Comment

by:grg99
ID: 7981180
Are we supposed to do this in a Ramunajan-like number-theoretic fashion, or by brute force trial and error?

If by brute force, my computer figured out the answer to (1) in about 20 seconds.

   The answer I get is: 45360

For #2, it will probably take my computer more time than the Universe has left, so I will leave that one to the mathematicians.

Regards,


George

0
 
LVL 18

Author Comment

by:deighton
ID: 7982042
I make it that that number has 100 factors, but I asked for 1,000 - so you'll need to do a bit more processing.

Yes you could get the answer to 1 by computing, it might take days or weeks.

My friend has a postulated solution for both, devised by reasoning, it has no rigorous proof though.
0
 
LVL 22

Expert Comment

by:grg99
ID: 7982437
Oh, silly me, and now I'm not near my computer.
Also I've found two much faster algorithms for doing this, so, the 100 million factors run may not be as impossible as I first thought...

More results this evening.

0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 56

Expert Comment

by:andyalder
ID: 7982933
Hint, it is bigger than 245044800 which has 1008 factors and is the smallest number with at least 1000 factors.

http://home.earthlink.net/~mrob/pub/math/numbers-8.html
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 7985545
deighton
The answer I get for part (1) is 561330000, part (2) takes a little more time but can be done by hand if given time. What prize are they offering? :-)

GwynforWeb
0
 
LVL 18

Author Comment

by:deighton
ID: 7986166
I make it that 561330000 has 700 factors, not 1,000
0
 
LVL 18

Author Comment

by:deighton
ID: 7986791
seems tha Q2 should have read

2) how many prime factors does the first number to have 1,000,000 factors have
0
 
LVL 2

Expert Comment

by:Mennovdh
ID: 7987254
answer to (1) is 11000...

you do mean 1000 binary, don't you?
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 7987604
deighton,
   How do you get that 561330000 has 700 factors? I am getting exactly 1000 factors and I have checked my calculations. (My algorithm reproduces the result grg99 gave for 100 numbers.)

    561330000=(2^4)*(3^4)*(5^4)*7*9*11

which by estimation has 5*5*5*2*2*2=1000 factors including itself and 1. How are you defining a factor?

GwynforWeb
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 7987837
I am fairly sure the answer to 2 is 19 prime factors (including 1) but I want to check my calculations which I will do later today.
0
 
LVL 18

Author Comment

by:deighton
ID: 7987856
a factor z of x means that 1<= z <=x where z divides exactly into z

x and z are integers

0
 
LVL 18

Author Comment

by:deighton
ID: 7987857
here's the 700 factors of the number you gave me.

1   1
2   2
3   3
4   4
5   5
6   6
7   7
8   8
9   9
10   10
11   11
12   12
13   14
14   15
15   16
16   18
17   20
18   21
19   22
20   24
21   25
22   27
23   28
24   30
25   33
26   35
27   36
28   40
29   42
30   44
31   45
32   48
33   50
34   54
35   55
36   56
37   60
38   63
39   66
40   70
41   72
42   75
43   77
44   80
45   81
46   84
47   88
48   90
49   99
50   100
51   105
52   108
53   110
54   112
55   120
56   125
57   126
58   132
59   135
60   140
61   144
62   150
63   154
64   162
65   165
66   168
67   175
68   176
69   180
70   189
71   198
72   200
73   210
74   216
75   220
76   225
77   231
78   240
79   243
80   250
81   252
82   264
83   270
84   275
85   280
86   297
87   300
88   308
89   315
90   324
91   330
92   336
93   350
94   360
95   375
96   378
97   385
98   396
99   400
100   405
101   420
102   432
103   440
104   450
105   462
106   486
107   495
108   500
109   504
110   525
111   528
112   540
113   550
114   560
115   567
116   594
117   600
118   616
119   625
120   630
121   648
122   660
123   675
124   693
125   700
126   720
127   729
128   750
129   756
130   770
131   792
132   810
133   825
134   840
135   875
136   880
137   891
138   900
139   924
140   945
141   972
142   990
143   1000
144   1008
145   1050
146   1080
147   1100
148   1125
149   1134
150   1155
151   1188
152   1200
153   1215
154   1232
155   1250
156   1260
157   1296
158   1320
159   1350
160   1375
161   1386
162   1400
163   1458
164   1485
165   1500
166   1512
167   1540
168   1575
169   1584
170   1620
171   1650
172   1680
173   1701
174   1750
175   1782
176   1800
177   1848
178   1875
179   1890
180   1925
181   1944
182   1980
183   2000
184   2025
185   2079
186   2100
187   2160
188   2200
189   2250
190   2268
191   2310
192   2376
193   2430
194   2475
195   2500
196   2520
197   2625
198   2640
199   2673
200   2700
201   2750
202   2772
203   2800
204   2835
205   2916
206   2970
207   3000
208   3024
209   3080
210   3150
211   3240
212   3300
213   3375
214   3402
215   3465
216   3500
217   3564
218   3600
219   3645
220   3696
221   3750
222   3780
223   3850
224   3888
225   3960
226   4050
227   4125
228   4158
229   4200
230   4375
231   4400
232   4455
233   4500
234   4536
235   4620
236   4725
237   4752
238   4860
239   4950
240   5000
241   5040
242   5103
243   5250
244   5346
245   5400
246   5500
247   5544
248   5625
249   5670
250   5775
251   5832
252   5940
253   6000
254   6075
255   6160
256   6237
257   6300
258   6480
259   6600
260   6750
261   6804
262   6875
263   6930
264   7000
265   7128
266   7290
267   7425
268   7500
269   7560
270   7700
271   7875
272   7920
273   8019
274   8100
275   8250
276   8316
277   8400
278   8505
279   8750
280   8910
281   9000
282   9072
283   9240
284   9450
285   9625
286   9720
287   9900
288   10000
289   10125
290   10206
291   10395
292   10500
293   10692
294   10800
295   11000
296   11088
297   11250
298   11340
299   11550
300   11664
301   11880
302   12150
303   12375
304   12474
305   12600
306   13125
307   13200
308   13365
309   13500
310   13608
311   13750
312   13860
313   14000
314   14175
315   14256
316   14580
317   14850
318   15000
319   15120
320   15400
321   15750
322   16038
323   16200
324   16500
325   16632
326   16875
327   17010
328   17325
329   17500
330   17820
331   18000
332   18225
333   18480
334   18711
335   18900
336   19250
337   19440
338   19800
339   20250
340   20412
341   20625
342   20790
343   21000
344   21384
345   22000
346   22275
347   22500
348   22680
349   23100
350   23625
351   23760
352   24300
353   24750
354   24948
355   25200
356   25515
357   26250
358   26730
359   27000
360   27216
361   27500
362   27720
363   28350
364   28875
365   29160
366   29700
367   30000
368   30375
369   30800
370   31185
371   31500
372   32076
373   32400
374   33000
375   33264
376   33750
377   34020
378   34650
379   35000
380   35640
381   36450
382   37125
383   37422
384   37800
385   38500
386   39375
387   39600
388   40095
389   40500
390   40824
391   41250
392   41580
393   42000
394   42525
395   42768
396   44550
397   45000
398   45360
399   46200
400   47250
401   48125
402   48600
403   49500
404   49896
405   50625
406   51030
407   51975
408   52500
409   53460
410   54000
411   55000
412   55440
413   56133
414   56700
415   57750
416   58320
417   59400
418   60750
419   61875
420   62370
421   63000
422   64152
423   66000
424   66825
425   67500
426   68040
427   69300
428   70000
429   70875
430   71280
431   72900
432   74250
433   74844
434   75600
435   77000
436   78750
437   80190
438   81000
439   81648
440   82500
441   83160
442   85050
443   86625
444   89100
445   90000
446   91125
447   92400
448   93555
449   94500
450   96250
451   97200
452   99000
453   99792
454   101250
455   102060
456   103950
457   105000
458   106920
459   110000
460   111375
461   112266
462   113400
463   115500
464   118125
465   118800
466   121500
467   123750
468   124740
469   126000
470   127575
471   128304
472   133650
473   135000
474   136080
475   138600
476   141750
477   144375
478   145800
479   148500
480   149688
481   151875
482   154000
483   155925
484   157500
485   160380
486   162000
487   165000
488   166320
489   170100
490   173250
491   178200
492   182250
493   185625
494   187110
495   189000
496   192500
497   198000
498   200475
499   202500
500   204120
501   207900
502   210000
503   212625
504   213840
505   222750
506   224532
507   226800
508   231000
509   236250
510   243000
511   247500
512   249480
513   255150
514   259875
515   267300
516   270000
517   277200
518   280665
519   283500
520   288750
521   291600
522   297000
523   299376
524   303750
525   311850
526   315000
527   320760
528   330000
529   334125
530   340200
531   346500
532   354375
533   356400
534   364500
535   371250
536   374220
537   378000
538   385000
539   400950
540   405000
541   408240
542   415800
543   425250
544   433125
545   445500
546   449064
547   455625
548   462000
549   467775
550   472500
551   486000
552   495000
553   498960
554   510300
555   519750
556   534600
557   556875
558   561330
559   567000
560   577500
561   594000
562   607500
563   623700
564   630000
565   637875
566   641520
567   668250
568   680400
569   693000
570   708750
571   729000
572   742500
573   748440
574   770000
575   779625
576   801900
577   810000
578   831600
579   850500
580   866250
581   891000
582   898128
583   911250
584   935550
585   945000
586   990000
587   1002375
588   1020600
589   1039500
590   1063125
591   1069200
592   1113750
593   1122660
594   1134000
595   1155000
596   1215000
597   1247400
598   1275750
599   1299375
600   1336500
601   1386000
602   1403325
603   1417500
604   1458000
605   1485000
606   1496880
607   1559250
608   1603800
609   1670625
610   1701000
611   1732500
612   1782000
613   1822500
614   1871100
615   1890000
616   2004750
617   2041200
618   2079000
619   2126250
620   2227500
621   2245320
622   2310000
623   2338875
624   2430000
625   2494800
626   2551500
627   2598750
628   2673000
629   2806650
630   2835000
631   2970000
632   3118500
633   3189375
634   3207600
635   3341250
636   3402000
637   3465000
638   3645000
639   3742200
640   3898125
641   4009500
642   4158000
643   4252500
644   4455000
645   4490640
646   4677750
647   5011875
648   5103000
649   5197500
650   5346000
651   5613300
652   5670000
653   6237000
654   6378750
655   6682500
656   6930000
657   7016625
658   7290000
659   7484400
660   7796250
661   8019000
662   8505000
663   8910000
664   9355500
665   10023750
666   10206000
667   10395000
668   11226600
669   11694375
670   12474000
671   12757500
672   13365000
673   14033250
674   15592500
675   16038000
676   17010000
677   18711000
678   20047500
679   20790000
680   22453200
681   23388750
682   25515000
683   26730000
684   28066500
685   31185000
686   35083125
687   37422000
688   40095000
689   46777500
690   51030000
691   56133000
692   62370000
693   70166250
694   80190000
695   93555000
696   112266000
697   140332500
698   187110000
699   280665000
700   561330000
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 7988153
deighton
   Oops I can not count.  For 100,000,000 factors  I am fairly sure the smallest number is

(2^9)*((3*5*7*11*13*17*19)^4)*(23*29*31*37*41*43*47)

which has a total of 15 prime factors excluding 1
0
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 200 total points
ID: 7988320
deighton  
  For some reason today I think 9 is a prime, try this

810810000=(2^4)*(3^4)*(5^4)*7*11*13

which does have 5*5*5*2*2*2=1000 factors
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 7989780
deighton
  To summarise all of this

Part 1

      810810000=(2^4)*(3^4)*(5^4)*7*11*13

Part 2

    15 prime factors excluding 1, with the number being

    (2^9)*((3*5*7*11*13*17*19)^4)*(23*29*31*37*41*43*47)

 

(The logic behind all of this is based on that if a number A is expressed in terms of its prime factors as

A=(P1^n1)(P2^n2)......(Pi^ni)

then A has (n1+1)(n2+1).....(ni+1) factors.
 
  The trick is now to choose the primes and powers such that A is a small as posiible  with (n1+1)(n2+1).....(ni+1) either being 1,000 or 100,000,000

GwynforWeb
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 8011194
Deighton, Thanks, GwynforWeb

 
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses
Course of the Month12 days, 8 hours left to enroll

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question