[math-fun] re one-to-one relation (odd partitions) <-> (non-repeat partitions)
Answer: (from Hardy and Wright) given n = l1 * 1 + l2 * 3 + l3 * 5 + l7 * 7 + ..., a ptn into odd parts, write each li in binary, e.g. li = 2^a1 + 2^a2 + 2^a3 + ... where the aj's are all different then expand n = (2^a1 * 1 + ...)*1 + ... by removing the brackets and we get a partition into distinct parts NJAS
Cute! test=Cases[Partitions[13],q_/;FreeQ[q,_?EvenQ]] {{13},{11,1,1},{9,3,1},{9,1,1,1,1},{7,5,1},{7,3,3},{7,3,1, 1,1},{7,1,1,1,1,1,1},{5,5,3},{5,5,1,1,1},{5,3,3,1, 1},{5,3,1,1,1,1,1},{5,1,1,1,1,1,1,1,1},{3,3,3,3, 1},{3,3,3,1,1,1,1},{3,3,1,1,1,1,1,1,1},{3,1,1,1,1,1, 1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1,1,1,1}} bi[n_Integer]:= DeleteCases[(2^Range[Length[#1]-1,0,-1]*# &)[IntegerDigits[n,2]],0] sloane[li:{__Integer}]:= Reverse[Sort[Flatten[z[bi[Length[#]],First[#]]&/@ Split[li]/.z->Times]]] enaols[li:{__Integer}]:= Reverse[Sort[li //. q_?EvenQ -> Sequence[q/2,q/2] ]] res=sloane/@ test {{13},{11,2},{9,3,1},{9,4},{7,5,1},{7,6},{7,3,2,1},{7,4, 2},{10,3},{10,2,1},{6,5,2},{5,4,3,1},{8,5},{12,1},{6,4, 3},{6,4,2,1},{8,3,2},{8,4,1}} enaols/@ res {{13},{11,1,1},{9,3,1},{9,1,1,1,1},{7,5,1},{7,3,3},{7,3,1, 1,1},{7,1,1,1,1,1,1},{5,5,3},{5,5,1,1,1},{5,3,3,1, 1},{5,3,1,1,1,1,1},{5,1,1,1,1,1,1,1,1},{3,3,3,3, 1},{3,3,3,1,1,1,1},{3,3,1,1,1,1,1,1,1},{3,1,1,1,1,1, 1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1,1,1,1}} sloane/@ % {{13},{11,2},{9,3,1},{9,4},{7,5,1},{7,6},{7,3,2,1},{7,4, 2},{10,3},{10,2,1},{6,5,2},{5,4,3,1},{8,5},{12,1},{6,4, 3},{6,4,2,1},{8,3,2},{8,4,1}} the reverse operation is amazing: just keep splitting any even number into halves until no evens remain! W. ----- Original Message ----- From: "N. J. A. Sloane" <njas@research.att.com> To: <math-fun@mailman.xmission.com>; <wouter.meeussen@pandora.be>; <wouter.meeussen@vandemoortele.com>; <wouter.meeussen@pandora.be> Sent: Saturday, August 20, 2005 6:02 PM Subject: [math-fun] re one-to-one relation (odd partitions) <-> (non-repeatpartitions) Answer: (from Hardy and Wright) given n = l1 * 1 + l2 * 3 + l3 * 5 + l7 * 7 + ..., a ptn into odd parts, write each li in binary, e.g. li = 2^a1 + 2^a2 + 2^a3 + ... where the aj's are all different then expand n = (2^a1 * 1 + ...)*1 + ... by removing the brackets and we get a partition into distinct parts NJAS _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
[re-sent for mistyped header--apologies if duplicated] wouter> the reverse operation is amazing:
just keep splitting any even number into halves until no evens remain!
And the inverse of *that* is: Keep pairwise adding repeated parts until no pairs remain. There are *two* similar bijections of not-all-odd with not-all-different. Note that the original can be phrased: parts differ by at least 1 <-> parts = +-1 mod 4. It's also true that parts differ by at least 2 <-> parts = +-1 mod 5. Good luck with *that* bijection! Now that the cat is out of the bag, I hope Andrew Granville won't mind me publicly stating that his modular reciprocal theorem is news to me and worthy of Knuth's attention as a candidate exercise for Volume II. --Bill Gosper PS: I just rediscovered the denesting of sqrt(4^(1/5)-3^(1/5)). I probably mentioned it the first time. If not, it's a decent puzzle.
participants (3)
-
N. J. A. Sloane -
R. William Gosper -
wouter meeussen