Talk:Factor-perfect numbers
A034776?
Can anyone here explain to me what A034776 is?
n a(n) factors g(n)
1 1 {1} 1
2 2 {1,2} 1
3 3 {1,3} 1
4 4 {1,2,4} 2
5 8 {1,5} 1
6 13 {1,2,3,6} 3
7 16 {1,7} 1
8 20 {1,2,4,8} 4
9 26 {1,3,9} 2
10 32 {1,2,5,10} 3
11 44 {1,11} 1
12 48 {1,2,3,4,6,12} 8
a(n) is aka A034776, g(n) is aka A074206 - I cannot think of any formula or logic to get those a(n). --Petelomax (talk) 05:28, 7 October 2022 (UTC)
g(n) seems to be more or less what the task here has to run to get the answers (note the 48 in about the 48th place in A074206). But a(n) feels like a troll of those who search for puzzle hints. --Wherrera (talk) 06:41, 7 October 2022 (UTC)
a(n) is Project Euler 548. g(n) = 1/(2-zeta(n)).--Nigel Galloway (talk) 13:40, 7 October 2022 (UTC)
As stated on PE548, g(12)=8, g(48)=48 and g(120)=132 - but A034776 has 48, 3408, and 222528 for those g(n) erm, a(n) - note that I don't have a problem with A074206, but I do with A034776. Also, my pathetic attempts to implement g(n)=1/(2-zeta(n)) gave me
{1,0}
{2,2.81637833}
{3,1.253222196}
{4,1.089708312}
{5,1.038343702}
zeta?
Is there some shortcut to calculating the sequence order using the zeta function? Supposedly solving zeta(n) = 2 should help, but I was not able to find anything to work using floating point real n and zeta(n).
suggested rewording
I found the third paragraph a bit hard to digest, and suggest replacing
For example, for the factorization of 6, if the first type of sequence is [1, 6], this is generated by [6] since 1 * 6 = 6. Similarly, the first type of sequence [1, 2, 6] is generated by the second type of sequence [2, 3] because 1 * 2 = 2 and 2 * 3 = 6. Similarly, [1, 3, 6] is generated by [3, 2] because 1 * 3 = 3 and 3 * 2 = 6.
with
For example, for the factorization of 6, if some element of the first type is [1, 2], it is matched by [2, 3] in the second type, with the leading 1 removed and a final element added if needed to reach the target, and likewise [1, 3] is matched [3, 2]. A first type [1,2,4,24] matches [2,2,6,2] which perhaps more clearly shows the multiplication steps and the fact that the product of the second type is always exactly equal to the target. Note that [1,6] in the first type is matched by [6] in the second, with no need to add a final element because it has already reached the target [aka an otherwise logical final 1 is not wanted]. Lastly the lengths of elements of the second type should always exactly match those of the first, except in the [1, n] case.
Let me know if you think that's better, worse, or needs any further improvement.
There is also apparently some confusion over whether the first type should end with the target, Julia does not (and Phix slavishly copies that) whereas Python and Wren do, and obviously I've based that rewording on a "not". --Petelomax (talk) 18:10, 7 October 2022 (UTC)
Yes, it could be optional as is the leading [1, ..], but for consistency with the task description I changed it in the Julia task. I also added a less memory-hogging way of getting the number of factorizations to the Julia example, though the Julia program still had to run overnight for 2342912. You can edit the task third paragraph if it is clearer that way-- go ahead. --Wherrera (talk) 18:24, 7 October 2022 (UTC)
Nah, thanks, I can spot a poisoned chalice, not like I know what I'm talking about anyway. 😜 --Petelomax (talk) 19:12, 7 October 2022 (UTC)
Sorry if it was not clear enough. I find the descriptions in the OEIS vague too. --Wherrera (talk) 20:43, 7 October 2022 (UTC)
Erdos' algorithm is the faster method
I updated the examples to reflect Erdos' algorithm on the first page of the referenced paper. --Wherrera (talk) 00:57, 8 October 2022 (UTC)
- Atempting to run the latest Julia entry, I get "ArgumentError: reducing over an empty collection is not allowed", same on https://julialang.org/learning/tryjulia/ - I am running
1.7.2, would installing1.8.2fix it?--Petelomax (talk) 14:33, 9 October 2022 (UTC)
Ok, but what is F?
Currently, the task page says:
- According to the paper listed below by P. Erdos, the number of these sequences is
However, there's no accompanying definition for F. Reviewing the first page of the linked paper where this expression occurs yields an incomplete definition for F (what is cn? What is o?) --Rdm (talk) 12:31, 9 October 2022 (UTC)
- Indeed, don't anyone take this too heavily, but some people should perhaps bear in mind that the purpose of rosettacode is to compare programming languages, rather than test the math proficiency of individual contributors. The two other linked references are almost completely incomprehensible to me: the Klazar/Luca paper seems to be about the theoretical bounds of some unspecified function, albeit at least a relevant one, whereas I cannot identify a single reason why wp:Enumerative combinatorics is any more pertinent than say Counting --Petelomax (talk) 13:54, 9 October 2022 (UTC)
F(n) is the number of different factorizations according to the second definition. I will add that, sorry for the lack of explanation. I don't usually try to fully understand the math papers either, I just look for the formulas they prove for useful hints. --Wherrera (talk) 17:51, 9 October 2022 (UTC)
wp link deleted
I have deleted the "see also" link to Wikipedia: Enumerative Combinatorics because that page contains nothing pertinent to this task. --Petelomax (talk)
- I think rc has a problem with tasks where a schoolboy with a pencil could do better than the solutions presented. There are many of them and my time is limited, a loop over the set of integers testing each to see if it meets the tasks requirements is I think a dumb solution, so I added a link to a Wikipedia entry which I think describes an intelligent solution. To work it requires a generating function which this task supplies as F(n). As any schoolboy worth the effort of educating (better the rest are just sent out to play football) will tell you functions of this form depend only on the characterization of n's prime decomposition. So let n=P1A1*P2A2 ... PkAk. 48 is 3*24 so let me consider those n such that the sum of A1..A5 is less than 6.
A1 A2 A3 A4 A5 nmin F(n) 1 0 0 0 0 2 1 2 0 0 0 0 4 2 1 1 0 0 0 6 3 3 0 0 0 0 8 4 2 1 0 0 0 12 8 1 1 1 0 0 30 13 4 0 0 0 0 16 8 3 1 0 0 0 24 20 2 2 0 0 0 36 26 2 1 1 0 0 60 44 1 1 1 1 0 210 75 5 0 0 0 0 32 16 4 1 0 0 0 48 48 3 2 0 0 0 72 76 3 1 1 0 0 120 132 2 2 1 0 0 180 176 2 1 1 1 0 420 308 1 1 1 1 1 2310 541
nmin is 2A1*3A2*5A3*7A4*11A5. 7*974 has the same characteristic as 3*24 so without further calculation I suggest F(619704967) is 48. Interestingly, the above table suggests that F(n) is odd only if all A are 1. I think I can prove this and that no such factorization meets the task requirements, which implies that n cannot be odd. See Talk:Untouchable numbers#Nice_rec for similar logic and 9 billion names of God the integer for A1..Ak.--Nigel Galloway (talk) 13:06, 23 March 2023 (UTC)
How about counting directed knots connecting in Hasse-Diagram
48 = 2^4 * 3 48-24--12---6---3 | | | | | ^ | | | | | ^ factor 3 ( prime b ) | | | | | ^ 16--8---4---2---1 < factor 2 (prime a) ^4 ^3 ^2 ^1 (pot of prime a ) Starting in knot 1 and than only to knots that increase the distance to 1 like and don't change side (prime-factor) more than once. 1->2->6->12->24->48 or 1->48, 1->12->48 , 1->2->4->8->16->48 or 1->6->24->48 but not 1->3->4->24->48
But one advantage is, that one solution of a primfactorisation a^n*b^m .. gives always the same solution.
Constructing p1**n *p2xp3xp3...
Most of the Factor-perfect numbers are of a form p1**n *p2xp3xp3
Using bigint will probably find new ones.
program MulPart;
//https://mathworld.wolfram.com/OrderedFactorization.html
{$IFDef WINDOWS}
{$APPTYPE Console}
{$ENDIF}
{$IFDEF FPC }
{$R+,I+,O+}
{$MODE Delphi}
{$OPTIMIZATION On,ALL}
{$ENDIF}
uses
SysUtils ;
type
tPrimes = array[0..31] of Uint32;
var
Primes: tPrimes;
powers: array[0..31] of byte;
P1xxNxP2 : Array[0..59] of Uint64;
P1xxNxP2xP3 : Array[0..52] of Uint64;
P1xxNxP2xP3xP4 : Array[0..47] of Uint64;
P1xxNxP2xP3xP4xP5 : Array[0..42] of Uint64;
P1xxNxP2xP3xP4xP5xP6 : Array[0..37] of Uint64;
PrimFacCnt : integer;
procedure Calc_P1xxNxP2;
// p1^x *p2*p3*p4*p5*p6
var
p , f1,f2, p1: UInt64;
i : integer;
begin
P1xxNxP2[0] := 1;
// 2^i*3 ->6,12,24,48... -> factor sequences 3/8/20/48 ...
p := 1;
For i := 1 to High(P1xxNxP2) do
Begin
P1xxNxP2[i] := 2*(P1xxNxP2[i-1])+p;
p +=p;
end;
// 2^i*3*5 ->30,60,120,... -> factor sequences 13/44/132/ ...
P1xxNxP2xP3[0] := 3;
p := 1;
f1 := 4;
For i := 1 to High(P1xxNxP2xP3) do
Begin
p1 := P1xxNxP2[i];
P1xxNxP2xP3[i] := f1*p1+p;
p += p1;
f1+= 1;
end;
// 2^i*3*5*7 ->210,420,840,... -> factor sequences 75/308/1076/ ...
// 75 5 *13+3*3 +1
// +1 +2 +3
p := 1;
f1 := 5;
f2 := 3;
For i := 1 to High(P1xxNxP2xP3xP4) do
Begin
p1 := P1xxNxP2[i];
P1xxNxP2xP3xP4[i] := f1*P1xxNxP2xP3[i]+f2*p1+p;
f1 +=1;
f2 +=2;
p += p1;
end;
// 2^i*3*5*7*11 ->2310,4620,9240,... -> factor sequences 541/2612/10404/ ...
// 3 13 75 541 7* 75 + 1*13+1*3
// 8 44 308 2612 8*308 + 3*44+2*8
// 20 132 1076 10404 9*1076 +5*132+3*20
p := 1;
f1 := 7;
f2 := 1;
For i := 1 to High(P1xxNxP2xP3xP4xP5) do
Begin
P1xxNxP2xP3xP4xP5[i] :=f1*P1xxNxP2xP3xP4[i]+f2*P1xxNxP2xP3[i]+p*P1xxNxP2[i];
f1 +=1;
f2 +=2;
p += 1;
end;
// 3 13 75 541 4683 8*541 +4* 75 +4*13+1*3
// 8 44 308 2612 25988 9*2612 +7*(308+44)+2*8
// 20 132 1076 10404 116180 10*10404+10*(1076+132)+3*20
p := 1;
f1 := 8;
f2 := 4;
For i := 1 to High(P1xxNxP2xP3xP4xP5xP6) do
Begin
P1xxNxP2xP3xP4xP5xP6[i] :=f1*P1xxNxP2xP3xP4xP5[i]+f2*(P1xxNxP2xP3xP4[i]+P1xxNxP2xP3[i])+p*P1xxNxP2[i];
IF P1xxNxP2xP3xP4xP5xP6[i] <P1xxNxP2xP3xP4xP5xP6[i-1] then
begin writeln(i-1:10);halt;end;
f1 +=1;
f2 +=3;
p += 1;
end;
end;
procedure OutPow(const pr:tPrimes);
var
i,cnt :integer;
begin
cnt := PrimFacCnt-1;
IF cnt<0 then
EXIT;
For i := 0 to cnt-1 do
if powers[i] = 1 then
write(pr[i],'*')
else
write(pr[i],'^',powers[i],'*');
if powers[cnt] = 1 then
write(pr[cnt])
else
write(pr[cnt],'^',powers[cnt]);
end;
procedure GetPrimeDecomp(n: UInt64);
const
wheeldiff: array [0 .. 7] of Uint32 = (+6, +4, +2, +4, +2, +4, +6, +2);
var
p: Int64;
i,pow,flipflop : integer;
begin
IF n < 2 then
begin
PrimFacCnt := 0;
powers[0] := 1;
exit;
end;
i := 0;
if Not(ODD(n))then
begin
Primes[i] := 2;pow := 0;
repeat
n := n shr 1;
inc(pow);
until ODD(n);
powers[i] := pow;inc(i);
end;
if n MOD 3=0 then
begin
Primes[i] := 3;pow := 0;
repeat
n := n DIV 3;
inc(pow);
until n MOD 3 <> 0;
powers[i] := pow;inc(i);
end;
if n MOD 5=0 then
begin
Primes[i] := 5;pow := 0;
repeat
n := n DIV 5;
inc(pow);
until n MOD 5 <> 0;
powers[i] := pow; inc(i);
end;
p := 7;
flipflop := 6;
while p*p <= n do
Begin
if n MOD p=0 then
begin
Primes[i] := p;pow := 0;
repeat
n := n DIV p;
inc(pow);
until n MOD p <> 0;
powers[i] := pow;inc(i);
end;
flipflop := flipflop - 1;
if flipflop < 0 then
flipflop := 7;
p := p + wheeldiff[flipflop]
end;
if n > 1 then
begin
Primes[i] := n;
powers[i] := 1;
inc(i);
end;
PrimFacCnt := i;
end;
procedure CheckForFactorPerfect(p : pUint64;maxpow,maxcnt:integer);
var
max2pow,j : integer;
begin
For max2pow := 2 to maxpow-1 do
Begin
GetPrimeDecomp(p[max2pow]);
if powers[0] = max2pow then
begin
IF PrimFacCnt = maxcnt then
begin
j := maxcnt-1;
repeat
if powers[j] <> 1 then
BREAK;
dec(j);
until j <1;
if j =0 then
begin
write(p[max2pow]:20,' :');
OutPow(primes);
writeln;
end;
end;
end;
end;
writeln;
end;
begin
Calc_P1xxNxP2 ;
CheckForFactorPerfect(@P1xxNxP2,High(P1xxNxP2),2);
CheckForFactorPerfect(@P1xxNxP2xP3,High(P1xxNxP2xP3),3);
CheckForFactorPerfect(@P1xxNxP2xP3xP4,High(P1xxNxP2xP3xP4),4);
CheckForFactorPerfect(@P1xxNxP2xP3xP4xP5,High(P1xxNxP2xP3xP4xP5),5);
CheckForFactorPerfect(@P1xxNxP2xP3xP4xP5xP6,High(P1xxNxP2xP3xP4xP5xP6),6);
end.
- Output:
48 :2^4*3
1280 :2^8*5
28672 :2^12*7
11534336 :2^20*11
218103808 :2^24*13
73014444032 :2^32*17
1305670057984 :2^36*19
404620279021568 :2^44*23
2089670227099910144 :2^56*29
2496 :2^6*3*13
454656 :2^12*3*37
2342912 :2^14*11*13
57409536 :2^18*3*73
583041810432 :2^30*3*181
2624225017856 :2^32*13*47
1014849232437248 :2^40*13*71
4446425022726144 :2^42*3*337
84372124269019136 :2^46*11*109
365635994747142144 :2^48*3*433
1579637569300201472 :2^50*23*61
467515780104192 :2^34*3*47*193
46545625738641408 :2^40*3*103*137
967798930861457408 :2^44*7*29*271
34753216512 :2^18*3*7*59*107
5806013294837760 :2^28*3*5*23*71*883
Found:
Not found:
29808 = 2^4*3^4*23
<pre>
48 :2^4*3 //power 4 = 2*(3-1)
1280 :2^8*5 //power 8 = 2*(5-1)
28672 :2^12*7
11534336 :2^20*11
218103808 :2^24*13
73014444032 :2^32*17
1305670057984 :2^36*19
404620279021568 :2^44*23
.....
2^32972*16487 //power 32972 = 2*(16487-1)
2^32984*16493 //power 32984 = 2*(16493-1)
all 2^(2*(p2-1) * p2 where p2 is prime >2 are all Factor-perfect numbers