January 2009 - mathfun@mailman.xmission.com

Re: [math-fun] Coding + and = with digits inside an integer
by Eric Angelini 26 Jan '09

26 Jan '09

Hello Hans, ... gee, how fast ! > 13 1=001 > 17 1=+01 > 57 +00=0 > 58 +01=1 ... those look awful, don't they? The rest looks fine! Thanks, Best, É. -----Message d'origine----- De : Hans Havermann [mailto:pxp@rogers.com] Envoyé : lundi 26 janvier 2009 18:43 À : math-fun Objet : Re: [math-fun] Coding + and = with digits inside an integer Eric Angelini: > Thus, with the [4+;8=] convention, a valid 5-digit integer > would be, for instance, 14283. Or 14081. Or 18041 (1=0+1). > But not 24284 (2+2=+). Neither 04585 (no leading zero). Is there anything else in the following 154 "solutions" that should be excluded? 1 10=10 2 11=11 3 12=12 4 13=13 5 1+0=1 6 1+1=2 7 1+2=3 8 1+5=6 9 1+6=7 10 15=15 11 16=16 12 17=17 13 1=001 14 1=0+1 15 1=1+0 16 1=1=1 17 1=+01 18 19=19 19 20=20 20 21=21 21 22=22 22 23=23 23 2+0=2 24 2+1=3 25 2+3=5 26 2+5=7 27 2+7=9 28 25=25 29 26=26 30 27=27 31 2=002 32 2=0+2 33 2=1+1 34 2=2+0 35 2=2=2 36 2=+02 37 29=29 38 30=30 39 31=31 40 32=32 41 33=33 42 3+0=3 43 3+2=5 44 3+3=6 45 3+6=9 46 35=35 47 36=36 48 37=37 49 3=003 50 3=0+3 51 3=1+2 52 3=2+1 53 3=3+0 54 3=3=3 55 3=+03 56 39=39 57 +00=0 58 +01=1 59 +02=2 60 +03=3 61 +05=5 62 +06=6 63 +07=7 64 +0=00 65 +0=+0 66 +09=9 67 +1=01 68 +1=+1 69 +2=02 70 +2=+2 71 +3=03 72 +3=+3 73 +5=05 74 +5=+5 75 +6=06 76 +6=+6 77 +7=07 78 +7=+7 79 +9=09 80 +9=+9 81 50=50 82 51=51 83 52=52 84 53=53 85 5+0=5 86 5+1=6 87 5+2=7 88 55=55 89 56=56 90 57=57 91 5=005 92 5=0+5 93 5=2+3 94 5=3+2 95 5=+05 96 5=5+0 97 5=5=5 98 59=59 99 60=60 100 61=61 101 62=62 102 63=63 103 6+0=6 104 6+1=7 105 6+3=9 106 65=65 107 66=66 108 67=67 109 6=006 110 6=0+6 111 6=1+5 112 6=3+3 113 6=+06 114 6=5+1 115 6=6+0 116 6=6=6 117 69=69 118 70=70 119 71=71 120 72=72 121 73=73 122 7+0=7 123 7+2=9 124 75=75 125 76=76 126 77=77 127 7=007 128 7=0+7 129 7=1+6 130 7=2+5 131 7=+07 132 7=5+2 133 7=6+1 134 7=7+0 135 7=7=7 136 79=79 137 90=90 138 91=91 139 92=92 140 93=93 141 9+0=9 142 95=95 143 96=96 144 97=97 145 9=009 146 9=0+9 147 9=2+7 148 9=3+6 149 9=+09 150 9=6+3 151 9=7+2 152 9=9+0 153 9=9=9 154 99=99

1 0

[math-fun] Coding + and = with digits inside an integer
by Eric Angelini 26 Jan '09

26 Jan '09

Hello Math-fun, ... stupid idea, yesterday, to get asleep: Let's examine a 5-digit integer like abcde; if we decide that b is the + sign and d the = sign, we have the simple equation a+c=e. This equation has a lot of solutions (like 1+2=3 or 1+0=1) ... but once we have decided that (for instance) 4 is coding "+" and 8 is coding "=", we cannot use elsewhere (in the integer) the digits 4 and 8. Thus, with the [4+;8=] convention, a valid 5-digit integer would be, for instance, 14283. Or 14081. Or 18041 (1=0+1). But not 24284 (2+2=+). Neither 04585 (no leading zero). Questions: a) What is the best [x+;y=] coding in order to produce the biggest quantity of valid 5-digit integers? b) Same question for a 6-digit integer? c) Same question for a 7-digit integer? (where 1424386 --> 1+2+3=6 would now be valid too!) Best, É. (now asleep)

2 1

Re: [math-fun] Coding + and = with digits inside an integer
by Eric Angelini 26 Jan '09

26 Jan '09

I've just noticed that 18181 is valid too! (a rose is a rose is a rose) Best, É. -----Message d'origine----- De : math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] De la part de Eric Angelini Envoyé : lundi 26 janvier 2009 15:35 À : math-fun Objet : [math-fun] Coding + and = with digits inside an integer Hello Math-fun, ... stupid idea, yesterday, to get asleep: Let's examine a 5-digit integer like abcde; if we decide that b is the + sign and d the = sign, we have the simple equation a+c=e. This equation has a lot of solutions (like 1+2=3 or 1+0=1) ... but once we have decided that (for instance) 4 is coding "+" and 8 is coding "=", we cannot use elsewhere (in the integer) the digits 4 and 8. Thus, with the [4+;8=] convention, a valid 5-digit integer would be, for instance, 14283. Or 14081. Or 18041 (1=0+1). But not 24284 (2+2=+). Neither 04585 (no leading zero). Questions: a) What is the best [x+;y=] coding in order to produce the biggest quantity of valid 5-digit integers? b) Same question for a 6-digit integer? c) Same question for a 7-digit integer? (where 1424386 --> 1+2+3=6 would now be valid too!) Best, É. (now asleep) _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] count of terms in cyclotomic polynomial
by wouter meeussen 24 Jan '09

24 Jan '09

the count of terms in cyclotomic polynomial bigPhi(n,x), say c, and the largest prime factor of n, say p, are known to coïncide for all n except those in a beheaded A070537= [[ 1 ]] ,15,21,30,33,35,39,42,45... in which case p<c (conjecture) It seems that A070537 also equals the values of n where w(n) is *larger* than the largest prime factor of n. with w(n)=1+ InverseMoebiusTransform( seq_z ) with seq_z equal to the sequence defined by mu(n) Sum(d|n, phi(d) mu(d) ) we get p<c<w OR p=c=w I don't see an evident link, do you? Wouter. (* sequences seq_z and w(n) pending desimbicilisation *) ____________________________________________ Please ignore the Mathematica code below: w=1+invmoebius[Table[MoebiusMu[n] Fold[ EulerPhi[#2] MoebiusMu[#2]+#1&, 0, Divisors[n]],{n,100}]] and invmoebT[partiallist:{__Integer}]:=Block[{n=Length[partiallist]},Fold[#1+par tiallist[[#2]]&,0,Divisors[n]]]; invmoebius[argSeq:{__Integer}]:=Table[invmoebT[Take[argSeq,i]],{i,Length[arg Seq]}]; c=Table[Length[Cyclotomic[n,x]], {n,100}] p=Table[If[n===1,2,Part[FactorInteger[n],-1,1]], {n,100}] triad=Transpose[{c,p,w}] diff=Select[triad,UnsameQ@@#&] A070537=Flatten@ Position[triad,q_List/;UnsameQ @@ q] ____________________________________________

1 1

Re: [math-fun] Encoding sorted lists with duplicates
by Steve Witham 24 Jan '09

24 Jan '09

The entertainment so far has been that I found a solution to a problem, despite being fuzzy about the problem, by working out how to measure solutions, and having a very good solution I didn't like (unary, egads, pfeh) fall out of that. I want to say a few things about how to solve the problem that I learned after having solved it.* The length of a codeword is supposed to match the log of the probability of the corresponding event. That way, you minimize the *expected* length of messages. But this problem wasn't about the expected length, it was about minimizing the *maximum* length. So I felt outside my usual habits. But there are two ways to push the problem back into the probability model. One is, to realize that if all messages have the *same* length, then that's the maximum. More, if that's the least possible single length, then it's also the least possible maximum. But inventing wholistic codes for arrays is tricky, so I was trying to code individual numbers, which seems reasonable because the problem seems...homogeneous across the array. But, thinking about the *typical* distribution seemed unwise for this minimum-maximum problem. Second, the right analog to probability is that every distinct array has the same probability, just the inverse of the number of distinct arrays. In this case it was the number of choices, duplicates allowed, of r things (in this case deltas between entries in a sorted list) taken from n. With my example where r = 1e6 and n = 2^32, ( r + n - 1 )! 13,511,284 -------------- ~= 2 (1) r! ( n - 1 )! The probability of a value for one of the elements in the array is the fraction of possible arrays where that element has that value. If each element is encoded according to that probability, the message will have the right length. From (1) above, you can calculate the probability of a delta d. It's the ratio of the number of arrays after removing d from the problem, to the number before. The number r decreases by one for each delta, and the number n decreases by the size of the delta. ( r - 1 + n - 1 - d )! r! ( n - 1 )! ----------------------------------------- (2) ( r - 1 )! ( n - 1 - d)! ( r + n - 1 )! Canceling, factoring and rearranging a little... r ( r + n - 2 - d )! ( n - 1 )! ------------- --------------------------------- (3) ( r + n - 1 ) ( r + n - 2 )! ( n - 1 - d)! When d = 0, the first factor determines the minimum codeword size. For my example, about -log2( 1e6 / 2^32 ) ~= 12.07, where my code used a minimum of 13 bits. Since the cost is the log of (3), the costs of factors just add. The second factor is roughly d ( n - 1 - d/2 ) ( --------------- ) (4) ( r + n - 2 - d/2 ) So, very roughly, the cost of d is -log2( n/(r+n) ) * d. For the example that's -log2( 2^32 / (2^32 + 1e6) ) * d ~= d/2977 (vs. my code's d/4096). This is what dictates the unary part of the code. (The two costs turn out pretty close for the total d = n = 2^32: 1e6 * 12.07 + 2^32 / 2977 ~= 13,512,716 ** 1e6 * 13 + 2^32 / 4096 = 14,048,576 (5) ) What I've been calculating is the cost of the first delta in the list. But the numbers r and n tend to shrink proportionally as you go through the list, leaving the results the same--mostly & usually! But you can compare the number in (5) to the exponent of (1) as a final check. The code is a Golumb/Rice code, which implies that deltas in a sorted list have a geometric distribution, which I'm trying to rebend my intuition around. --Steve * "You can't fix a Lisp Machine by just power-cycling it with no understanding of what's going on!" ** Using a better estimate of the cost of the average first delta, -r*log2(r/(r+n-1))-n*log2((n-1-(n/r/2))/(n+r-2-(n/r/2))) ~= 13,511,294 -- off by only 10 bits.

1 0

[math-fun] Repunit Divisor Query
by Hans Havermann 24 Jan '09

24 Jan '09

The "lower central (median) divisor of n" (OEIS: A060775) is the largest divisor of n that is less than the square root of n. Empirically, for small k, the lower central divisor of repunit(6k), i.e. (10^(6*k)-1)/9, is (10^k - 1)(10^(2*k) - 10^k + 1)/3. The first few examples are: 273, 326733, 332667333, 333266673333, 333326666733333, etc. Is this ALWAYS so? Alternatively, is there a k for which the lower central divisor of (10^(6*k)-1)/9 is GREATER than (10^k - 1)(10^(2*k) - 10^k + 1)/3?

1 0

Re: [math-fun] Tiling puzzle
by Dan Asimov 22 Jan '09

22 Jan '09

I did mean to exclude those cases. (But maybe there's no need to, since they wouldn't have the two exceptions mentioned.) Also, even with all the technical nonsense, I neglected to specify that the N regular polygons must be congruent! So to summarize, I hope, more clearly: ********************************************************* * PUZZLE: There is a closed metric surface S that, for * * exactly eight values of N in the range 1 <= N <= 10, * * can be tiled by N congruent regular k-gons * * (where k may depend on N). * * * * Find a surface S satisfying this condition and * * prove that it works. * * * ********************************************************* --Dan Rich wrote: << Are you excluding the case of cutting the surface of a sphere into orange wedges? I'd view an orange wedge as a two-sided regular polygon, but opinions may vary. << Quoting Dan Asimov <dasimov(a)earthlink.net>: . . . ____________________________________________________________ > Notes: Closed means of finite extent and > without boundary. A tiling means S is the union > of regular polygons such that if P and Q are > distinct polygons, then their intersection > is either empty or a union of common vertices and/or edges. > Also, some of one polygon's own edges may coincide pairwise. > A regular polygon Q of k sides inherits its metric from S > such that the isometry group of Q has 2k elements. > > --Dan >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] integrate(floor(sqrt(x)))
by rwg＠sdf.lonestar.org 22 Jan '09

22 Jan '09

> The problem is just a typo: > In front of the fraction, the sign should be a minus, rather than a > plus. > > David GACK, it's more serious than a typo! I got it by plugging e=f=1 into a broken version of the identity Integrate[t^f*Floor[t]^e, {t, 0, x}] == (1/(1 + f))*(x^(1 + f)*Floor[x]^e + Sum[(-1)^i*Binomial[e, i]*(-HurwitzZeta[-1 - e - f + i, 1 + Floor[x]] + Zeta[-1 - e - f + i]), {i, e}]) == -((1/(1 + f))*((-x^(1 + f))*Floor[x]^e + Floor[x]^(1 + e + f) - Sum[Binomial[1 + f, i]*(-HurwitzZeta[-1 - e - f + i, Floor[x]] + HurwitzZeta[-1 - e - f + i, 0]), {i, 1 + f}])) where e or f is an integer and e,f>=0. Thanks Rich and David for catching this! --rwg > > ----- Original Message ----- > From: <rwg(a)sdf.lonestar.org> > ----- Original Message ----- > From: <rcs(a)xmission.com> > To: <math-fun(a)mailman.xmission.com> > Sent: Monday, January 19, 2009 20:29 > Subject: Re: [math-fun] integrate(floor(sqrt(x))) > > >> The first integral seems to have a problem when the upper limit >> x crosses the square of an integer: The integrand jumps, but the >> integral is continuous. (No problem yet.) But the RHS expression >> will have a big jump, as sqrt(x) crosses an integer value, and >> floor(sqrt(x)) jumps, and the positive product in the RHS jumps. >> What am I missing? >> >> Rich >> >> --------------------- >> >> Quoting rwg(a)sdf.lonestar.org: >> >>> It's very easy to "shew that" >>> >>> / x >>> [ >>> I floor(sqrt(t)) dt >>> ] >>> / 0 >>> (floor(sqrt(x)) + 1) (2 floor(sqrt(x)) >>> + 1) >>> = floor(sqrt(x)) (x >>> + -------------------------------------------), >>> 6 >>> but a little surprising when you look at it. >>> >>> / x >>> [ 3/2 >>> I sqrt(floor(t)) dt = floor (x) + x sqrt(floor(x)) >>> ] >>> / 0 >>> 1 >>> 1 >>> + hurwitz_zeta(- -, floor(x)) - >>> zeta(- -). >>> 2 >>> 2 >>> --rwg >>> >>> >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun(a)mailman.xmission.com >>> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >

1 0

[math-fun] Tiling puzzle
by Dan Asimov 22 Jan '09

22 Jan '09

PUZZLE: There is a closed metric surface S that can be tiled by N regular polygons for all but two values of N in the range 1 <= N <= 10. Find a surface S satisfying this condition and prove that it works. ____________________________________________________________ Notes: Closed means of finite extent and without boundary. A tiling means S is the union of regular polygons such that if P and Q are distinct polygons, then their intersection is either empty or a union of common vertices and/or edges. Also, some of one polygon's own edges may coincide pairwise. A regular polygon Q of k sides inherits its metric from S such that the isometry group of Q has 2k elements. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Gödel book
by Eric Angelini 22 Jan '09

22 Jan '09

Hello Gareth and Dan, ... < Echolaliste > is a french website dedicated to all kind of lists : « Le site de toutes les listes »: http://www.echolaliste.com/ ... the name of this site comes from the (rare) french word < écholalie >, which is a term used in psychology: http://www.cnrtl.fr/definition/écholalie (scroll at the bottom of the page): « Écholalie : répétition automatique, par un sujet, des paroles que vient de prononcer son interlocuteur. » (automatical repetition, by the subject, of the words just pronounced by his interlocutor) This is good quotefrom the above dictionary: « répétition de syllabes ou de mots. L'enfant les répète pour le plaisir de parler... C'est l'un des derniers restes du gazouillis des bébés... » (repetition of syllables or words. The kid repeats them for the pleasure of talking... It is a last remain of the baby's babbling) < Echolaliste > is filled with absurd/sound/funny lists of all kinds -- in the spirit of Mad Magazine (the good years --> 1967/1980 ;-) Hope this helps! (and I know of no "guère épais" list or group on line) Best, É. -----Message d'origine----- De : math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] De la part de Gareth McCaughan Envoyé : mercredi 21 janvier 2009 22:50 À : math-fun(a)mailman.xmission.com Objet : Re: [math-fun] Gödel book On Wednesday 21 January 2009, Dan Asimov wrote: [me:] > Is an echolaliste someone who suffers from echolalia? > And if so, how does the other half of the pun work? (Does > "echo" mean the same in French as in english, or does it > e.g. mean "behold" following Latin "ecce" or something? ) [Dan:] > Yeah. And also, Eric wrote: Are you saying "yes" to some or all of my questions, or saying that you too would like to know the answers? > Okay, thanks. Now is "guère épais" a group of some kind, like Oulipo ? A three-way pun there would be too much to expect, no? -- g _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0