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

Home > Just Math
A simple logical question (Posted on 2007-07-27) Difficulty: 2 of 5
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.)
Solution 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   end
10000   fnDivsors(X)
10001   local I,Dr,NPrm,N,Tct,PDr
10090   PrDivCt=0
10100   NPrm=0:N=X:PDr=0
10110   repeat
10120    Dr=prmdiv(N)
10125    if Dr=1 then goto 10195
10130    N=N//Dr
10135   PrDivCt=PrDivCt+1
10140    if Dr>PDr then
10150     :NPrm=NPrm+1:PrCt(NPrm)=1
10160    :else
10170     :PrCt(NPrm)=PrCt(NPrm)+1
10180    PDr=Dr
10190   until Dr=1
10195   Tct=1
10200   for I=1 to NPrm
10210     Tct=Tct*(PrCt(I)+1)
10220   next
10230   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   end
10000   fnDivsors(X)
10001   local I,Dr,NPrm,N,Tct,PDr
10100   NPrm=0:N=X:PDr=0
10110   repeat
10120    Dr=prmdiv(N)
10125    if Dr=1 then goto 10195
10130    N=N//Dr
10140    if Dr>PDr then
10150     :NPrm=NPrm+1:PrCt(NPrm)=1
10160    :else
10170     :PrCt(NPrm)=PrCt(NPrm)+1
10180    PDr=Dr
10190   until Dr=1
10195   Tct=1
10200   for I=1 to NPrm
10210     Tct=Tct*(PrCt(I)+1)
10220   next
10230   return(Tct)
 
with the result:
      x                                       d(x) d(d(x)) d(d(d(x))) # of prime factors  
4                                               3       2       2       2
16                                              5       2       2       4
64                                              7       2       2       6
1024                                            11      2       2       10
4096                                            13      2       2       12
65536                                           17      2       2       16
262144                                          19      2       2       18
4194304                                         23      2       2       22
268435456                                       29      2       2       28
1073741824                                      31      2       2       30
68719476736                                     37      2       2       36
1099511627776                                   41      2       2       40
4398046511104                                   43      2       2       42
70368744177664                                  47      2       2       46
4503599627370496                                53      2       2       52
288230376151711744                              59      2       2       58
1152921504606846976                             61      2       2       60
73786976294838206464                            67      2       2       66
1180591620717411303424                          71      2       2       70
4722366482869645213696                          73      2       2       72
302231454903657293676544                        79      2       2       78
4835703278458516698824704                       83      2       2       82
309485009821345068724781056                     89      2       2       88
79228162514264337593543950336                   97      2       2       96
1267650600228229401496703205376                 101     2       2       100
5070602400912917605986812821504                 103     2       2       102
81129638414606681695789005144064                107     2       2       106
324518553658426726783156020576256               109     2       2       108
5192296858534827628530496329220096              113     2       2       112
85070591730234615865843651857942052864          127     2       2       126
1361129467683753853853498429727072845824        131     2       2       130
87112285931760246646623899502532662132736       137     2       2       136
348449143727040986586495598010130648530944      139     2       2       138
356811923176489970264571492362373784095686656   149     2       2       148
1427247692705959881058285969449495136382746624  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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information