All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A simple logical question (Posted on 2007-07-27)
If d(x) denotes the no. positive divisors of x and d(d(d(x))), d(d(x)), d(x) and x can be arranged in 12 different ways. Find possible values of n(x), where n(x) is no. of prime factors of x. Also find possible values of x less than 100.

 See The Solution Submitted by Praneeth Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration--lacking proof--spoilers | Comment 1 of 4

If x, d(x), d(d(x)) and d(d(d(x))) can be arranged in 12 different ways, two must be the same and all others different, as 4!/2 = 12.

The below program finds numbers that meet the criteria, and reports on the number of prime factors, counting each prime factor each time it occurs, so for example, 16 has four prime factors, all of them equal to 2.

`    5   dim PrCt(12)   10   for N=1 to 20000   20    A=fnDivsors(N):PrSave=PrDivCt   30    B=fnDivsors(A)   40    C=fnDivsors(B)   50    MCt=0   60    if N=A then MCt=MCt+1   61    if N=B then MCt=MCt+1   62    if N=C then MCt=MCt+1   63    if A=B then MCt=MCt+1   64    if A=C then MCt=MCt+1   65    if B=C then MCt=MCt+1   70   if MCt=1 then print N,A,B,C,PrSave  100   next  999   end10000   fnDivsors(X)10001   local I,Dr,NPrm,N,Tct,PDr10090   PrDivCt=010100   NPrm=0:N=X:PDr=010110   repeat10120    Dr=prmdiv(N)10125    if Dr=1 then goto 1019510130    N=N//Dr10135   PrDivCt=PrDivCt+110140    if Dr>PDr then10150     :NPrm=NPrm+1:PrCt(NPrm)=110160    :else10170     :PrCt(NPrm)=PrCt(NPrm)+110180    PDr=Dr10190   until Dr=110195   Tct=110200   for I=1 to NPrm10210     Tct=Tct*(PrCt(I)+1)10220   next10230   return(Tct)`
`The results are:`
` x      d(x) d(d(x)) d(d(d(x))) # of prime factors 4       3       2       2       2 9       3       2       2       2 16      5       2       2       4 25      3       2       2       2 49      3       2       2       2 64      7       2       2       6 81      5       2       2       4 121     3       2       2       2 169     3       2       2       2 289     3       2       2       2 361     3       2       2       2 529     3       2       2       2 625     5       2       2       4 729     7       2       2       6 841     3       2       2       2 961     3       2       2       2 1024    11      2       2       10 1369    3       2       2       2 1681    3       2       2       2 1849    3       2       2       2 2209    3       2       2       2 2401    5       2       2       4 2809    3       2       2       2 3481    3       2       2       2 3721    3       2       2       2 4096    13      2       2       12 4489    3       2       2       2 5041    3       2       2       2 5329    3       2       2       2 6241    3       2       2       2 6889    3       2       2       2 7921    3       2       2       2 9409    3       2       2       2 10201   3       2       2       2 10609   3       2       2       2 11449   3       2       2       2 11881   3       2       2       2 12769   3       2       2       2 14641   5       2       2       4 15625   7       2       2       6 16129   3       2       2       2 17161   3       2       2       2 18769   3       2       2       2 19321   3       2       2       2`

the first seven lines of which answer the second part: the possible values of x less than 100, as we have all the possible values of x less than 20,000.

Each number is a power of a single prime number (I think the intent of the question on how many prime divisors was, how many different prime divisors, and that is just 1). Each is an even power of a prime number, and so is also a perfect square. The number in the last column above is in fact the power of the base prime.

Since, in dealing with these numbers, it doesn't really matter what the base prime is, the following program explores the powers of 2 as the base prime:

`     5   dim PrCt(12)   10   for Pwr=1 to 150   15    N=2^Pwr   20    A=fnDivsors(N):PrSave=PrCt(1)   30    B=fnDivsors(A)   40    C=fnDivsors(B)   50    MCt=0   60    if N=A then MCt=MCt+1   61    if N=B then MCt=MCt+1   62    if N=C then MCt=MCt+1   63    if A=B then MCt=MCt+1   64    if A=C then MCt=MCt+1   65    if B=C then MCt=MCt+1   70   if MCt=1 then print N;tab(48);A,B,C,PrSave  100   next  999   end10000   fnDivsors(X)10001   local I,Dr,NPrm,N,Tct,PDr10100   NPrm=0:N=X:PDr=010110   repeat10120    Dr=prmdiv(N)10125    if Dr=1 then goto 1019510130    N=N//Dr10140    if Dr>PDr then10150     :NPrm=NPrm+1:PrCt(NPrm)=110160    :else10170     :PrCt(NPrm)=PrCt(NPrm)+110180    PDr=Dr10190   until Dr=110195   Tct=110200   for I=1 to NPrm10210     Tct=Tct*(PrCt(I)+1)10220   next10230   return(Tct) with the result:`
`      x                                       d(x) d(d(x)) d(d(d(x))) # of prime factors  4                                               3       2       2       216                                              5       2       2       464                                              7       2       2       61024                                            11      2       2       104096                                            13      2       2       1265536                                           17      2       2       16262144                                          19      2       2       184194304                                         23      2       2       22268435456                                       29      2       2       281073741824                                      31      2       2       3068719476736                                     37      2       2       361099511627776                                   41      2       2       404398046511104                                   43      2       2       4270368744177664                                  47      2       2       464503599627370496                                53      2       2       52288230376151711744                              59      2       2       581152921504606846976                             61      2       2       6073786976294838206464                            67      2       2       661180591620717411303424                          71      2       2       704722366482869645213696                          73      2       2       72302231454903657293676544                        79      2       2       784835703278458516698824704                       83      2       2       82309485009821345068724781056                     89      2       2       8879228162514264337593543950336                   97      2       2       961267650600228229401496703205376                 101     2       2       1005070602400912917605986812821504                 103     2       2       10281129638414606681695789005144064                107     2       2       106324518553658426726783156020576256               109     2       2       1085192296858534827628530496329220096              113     2       2       11285070591730234615865843651857942052864          127     2       2       1261361129467683753853853498429727072845824        131     2       2       13087112285931760246646623899502532662132736       137     2       2       136348449143727040986586495598010130648530944      139     2       2       138356811923176489970264571492362373784095686656   149     2       2       1481427247692705959881058285969449495136382746624  151     2       2       150`

Of course all the prime factors are 2, so the count of prime factors is the power of 2. It would work with any prime factor.

The sequence of powers didn't look immediately obvious to me, so I looked it up in Sloane.  The numbers are of course all the numbers that are 1 less than a prime.

So the numbers that satisfy the criteria are all of the form p^n, where p is prime and n is 1 less than a prime.

 Posted by Charlie on 2007-07-27 12:13:58

 Search: Search body:
Forums (0)