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.
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 |
computer exploration--lacking proof--spoilers
