- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] "quadratic residue" division ??
by Henry Baker 26 Aug '17

26 Aug '17

How about this weird form of division (in maxima): qdivide(m,n):=block([q,r,q1,r1], q:floor(m/n), r:m-q*n, /* r is non-negative */ if is(jacobi(r,n)=-1) then (q1:q+1,r1:r-n) else (q1:q,r1:r), [q1,r1]); e.g., (%i25) qdivide(1,19); (%o25) [0, 1] (%i26) qdivide(2,19); (%o26) [1, - 17] (%i27) qdivide(3,19); (%o27) [1, - 16] (%i28) qdivide(4,19); (%o28) [0, 4] (%i29) qdivide(5,19); (%o29) [0, 5] (%i30) qdivide(6,19); (%o30) [0, 6] (%i31) qdivide(7,19); (%o31) [0, 7] (%i32) qdivide(8,19); (%o32) [1, - 11] (%i33) qdivide(9,19); (%o33) [0, 9] (%i34) qdivide(10,19); (%o34) [1, - 9] (%i35) qdivide(11,19); (%o35) [0, 11] (%i36) qdivide(12,19); (%o36) [1, - 7] (%i37) qdivide(13,19); (%o37) [1, - 6] (%i38) qdivide(14,19); (%o38) [1, - 5] (%i39) qdivide(15,19); (%o39) [1, - 4] (%i40) qdivide(16,19); (%o40) [0, 16] (%i41) qdivide(17,19); (%o41) [0, 17] (%i42) qdivide(18,19); (%o42) [1, - 1] (%i43) qdivide(19,19); (%o43) [1, 0] If we utilize this form of division for base conversion to a prime base p=3(mod 4), we automatically get a representation whose digits are +-r, where r is a quadratic residue (mod p). One obvious property: perfect +- symmetry: negation means negating every digit. Questions: Does anything interesting happen when this form of division is used in other places -- e.g., gcd algorithms? Does this type of division induce a slightly different "norm" s.t. the norm of the remainder is strictly < the norm of the divisor? I suspect that there is a close relationship with division in the Gaussian integers, but I haven't checked this yet.

1 0

[math-fun] Stupid quadratic residue question
by Henry Baker 24 Aug '17

24 Aug '17

For odd primes p=3 (mod 4), the number of residues & non-residues is equal, and every element of GF(p) can be represented as 0, r or -r, where r is a quadratic residue. Thus, if p=3, the representatives are 0,1,-1. If p=7, the representatives are 0,1,2,4,-1,-2,-4. If p=11, the representatives are 0,1,3,4,5,9,-1,-3,-4,-5,-9. So, are there any advantages to using *only* residues (or alternatively, non-residues) as *representatives* mod p? In particular, if we consider expressing integers *base p* for a base p=3(mod 4), and we utilize only residues and negative residues for our "digits", do any interesting patterns arise? E.g., for base p=3, the digits in this representation are simply Knuth's "trits". Is there already a name for this type of number base representation (We have to be a tad careful when doing the base conversion; I'm not worried about the complexity of the conversion itself for the moment.) Due to the strong analogy with positive & negative (real) numbers, there may be interesting analogues in matrix problems mod p using this representation.

1 0

[math-fun] Transfinite ordinals in Shakespeare
by Adam P. Goucher 23 Aug '17

23 Aug '17

There's an explicit reference to $\omega + 1$ in Shakespeare's the Taming of the Shrew, 1596 (emphasis mine): BIONDELLO I cannot tell; expect they are busied about a counterfeit assurance: take you assurance of her, 'cum privilegio ad imprimendum solum:' to the church; take the priest, clerk, and some sufficient honest witnesses: If this be not that you look for, I have no more to say, But bid Bianca farewell *for ever and a day*. Did this hold the record for the largest ordinal discovered until Cantor? Best wishes, Adam P. Goucher

4 4

Re: [math-fun] Transfinite ordinals in Shakespeare
by Henry Baker 23 Aug '17

23 Aug '17

This one's not quite transfinite, but I've always loved (economist) Herb Stein's: 'If something cannot go on forever, it will stop', which is equivalent to 'if something cannot go on forever, it must have a bound', which is the contrapositive of 'if something doesn't have a bound, then it must be infinite'. Herb Stein was actor Ben Stein's father; Ben Stein (naturally) played the economics teacher in Ferris Bueller's Day Off. At 01:06 AM 8/23/2017, Adam P. Goucher wrote: >There's an explicit reference to $\omega + 1$ in Shakespeare's >the Taming of the Shrew, 1596 (emphasis mine): > >BIONDELLO I cannot tell; expect they are busied about a > counterfeit assurance: take you assurance of her, > 'cum privilegio ad imprimendum solum:' to the > church; take the priest, clerk, and some sufficient > honest witnesses: If this be not that you look for, > I have no more to say, But bid Bianca farewell > *for ever and a day*. > >Did this hold the record for the largest ordinal discovered >until Cantor? > >Best wishes, > >Adam P. Goucher

1 0

Re: [math-fun] Mrs. Perkin's Quilt variation
by Dan Asimov 19 Aug '17

19 Aug '17

Actually, that's easy: Just tile the plane with squares of sides a and b in a repeating pattern like this |-------- | | | |-------- | | | ----------| | | | | | | |----------- | | | | -------| |--- | | etc. --------- and by connecting e.g. the centers of the 4 big squares shown we get a fundamental domain for the torus having side sqrt(a^2 + b^2), tiled by one a x a and one b x b square. SO . . . suppose some N in Z+ is equal to an arbitrary sum of not necessarily distinct integer squares: N = a_1^2 + ... + a_k^2 . Question: --------- When does that correspond to a tiling of the square torus of side sqrt(N) by one square each of sides a_1, ..., a_n, respectively. (with no condition on the orientation of the tiles) ??? —Dan ----- Usually when tiling a square is mentioned I think also of the corresponding question on a square torus. For the case of a square torus, it doesn't need to be integer-sided. E.g., the square torus of side sqrt5 can be tiled (edge-to-edge) by one 2 x 2 square and one 1 x 1 square. The sides of the tiles will *not* be parallel to the two perpendicular preferred directions on the torus (the sides of its underlying square). In general if J is an ideal* of the Gaussian integers Z[i], we can look at the square torus C / J , which has area = a^2 + b^2 and will contain a^2 + b^2 images of points in Z{i] by the quotient map. Question: --------- Will such a torus — WLOG, coming from the square with vertices at (0,0), (a,b), (-b,a), (a-b,a+b) — always be tilable by one square of side a and one square of side b ??? ----- -----

1 0

Re: [math-fun] Mrs. Perkin's Quilt variation
by Dan Asimov 19 Aug '17

19 Aug '17

Usually when tiling a square is mentioned I think also of the corresponding question on a square torus. For the case of a square torus, it doesn't need to be integer-sided. E.g., the square torus of side sqrt5 can be tiled (edge-to-edge) by one 2 x 2 square and one 1 x 1 square. The sides of the tiles will *not* be parallel to the two perpendicular preferred directions on the torus (the sides of its underlying square). In general if J is an ideal* of the Gaussian integers Z[i], we can look at the square torus C / J , which has area = a^2 + b^2 and will contain a^2 + b^2 images of points in Z{i] by the quotient map. Question: --------- Will such a torus — WLOG, coming from the square with vertices at (0,0), (a,b), (-b,a), (a-b,a+b) — always be tilable by one square of side a and one square of side b ??? ----- —Dan ————— * J will just be a rotated and uniformly scaled copy of Z{i] itself, anything of the form (a + bi) Z[i] for integers a and b. ----- This variant, obtained by flipping the rectangle in the lower-right corner, may be aesthetically more pleasing: +-----+---+---+ |a a a|b b|c c| | | | | |a a a|b b|c c| | +---+---+ |a a a|d d|e e| +---+-+ | | |f f|g|d d|e e| | +-+-+-+---+ |f f|h|i|j j j| +---+-+-+ | |k k|l l|j j j| | | | | |k k|l l|j j j| +---+---+-----+ Tom Tom Karzes writes: > I think I have a 12-tile solution for 7x7: > > +-----+---+---+ > |a a a|b b|c c| > | | | | > |a a a|b b|c c| > | +---+---+ > |a a a|d d|e e| > +---+-+ | | > |f f|g|d d|e e| > | +-+---+-+-+ > |f f|h h h|i|j| > +---+ +-+-+ > |k k|h h h|l l| > | | | | > |k k|h h h|l l| > +---+-----+---+ > > I don't know if this is optimal. > > Tom > > Allan Wechsler writes: > > Suppose you are asked to tile an integer square of side n with smaller > > squares, but the tiles are all of side 1, 2, or 3. What is the smallest > > number of tiles, a(n), that you can get away with? > > > > For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, > > 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct. > > > > If these values are right, then a(n) is not in OEIS. > > > > It's obvious that a(3k) = k^2. I would expect that big squares can be > > optimally tiled by filling most of the space with 3's, with a "fringe" of > > some sort around two sides if n is not a multiple of 3. But I maintain a > > small hope that there will be "weird" solutions that don't look like this. > > Can anybody provide more values? -----

2 1

Re: [math-fun] math-fun Digest, Vol 174, Issue 38
by Stuart Anderson 19 Aug '17

19 Aug '17

Silvia Heubach has some recursion formulae http://www.calstatela.edu/sites/default/files/users/u1231/Papers/cgtc30.pdf ------------------------------ Message: 3 Date: Fri, 18 Aug 2017 22:06:47 -0400 From: James Propp <jamespropp(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> Subject: Re: [math-fun] Mrs. Perkin's Quilt variation Message-ID: <CA+G9J-fDQ1aSb6biODvqCQ9DzFeTDBxkaAq9mZ8J5O1vx9iAww(a)mail.gmail.com> Content-Type: text/plain; charset="UTF-8" As a warm-up we might consider allowing only 1-by-1 and 2-by-2 tiles. In that case, minimizing the number of tiles is equivalent to maximizing the number of 2-by-2 tiles; that is, we're trying to disjointly pack as many 2-by-2 squares as possible into an n-by-n square. It's obvious that a(2k) = k^2. Can anyone prove that a(2k+1) = k^2+4k+1? Equivalently, can anyone prove that you can't pack more than k^2 2-by-2 squares inside a (2k+1)-by-(2k+1) square? Jim Propp On Friday, August 18, 2017, Allan Wechsler <acwacw(a)gmail.com> wrote: > Suppose you are asked to tile an integer square of side n with smaller > squares, but the tiles are all of side 1, 2, or 3. What is the smallest > number of tiles, a(n), that you can get away with? > > For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, > 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct. > > If these values are right, then a(n) is not in OEIS. > > It's obvious that a(3k) = k^2. I would expect that big squares can be > optimally tiled by filling most of the space with 3's, with a "fringe" of > some sort around two sides if n is not a multiple of 3. But I maintain a > small hope that there will be "weird" solutions that don't look like this. > Can anybody provide more values? > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > ------------------------------ Message: 4 Date: Fri, 18 Aug 2017 19:30:21 -0700 From: Tom Karzes <karzes(a)sonic.net> To: math-fun <math-fun(a)mailman.xmission.com> Subject: Re: [math-fun] Mrs. Perkin's Quilt variation Message-ID: <22935.41661.920082.734260(a)gargle.gargle.HOWL> Content-Type: text/plain; charset=us-ascii When n = 2k+1: Color the square with a 4-color checkerboard, with colors a, b, c, and d, as follows: Color the first row ababab..., color the second row cdcdcd..., then repeat after that, so for a 5x5 square (k=2) you get: ababa cdcdc ababa cdcdc ababa Observe that a given 2x2 tile will always cover exactly one of each of the 4 colors. Also observe that there are exactly k^2 cells with color d. Therefore k^2 is an upper bound on the number of 2x2 tiles that can be placed. Tom James Propp writes: > As a warm-up we might consider allowing only 1-by-1 and 2-by-2 tiles. In > that case, minimizing the number of tiles is equivalent to maximizing the > number of 2-by-2 tiles; that is, we're trying to disjointly pack as many > 2-by-2 squares as possible into an n-by-n square. It's obvious that a(2k) = > k^2. Can anyone prove that a(2k+1) = k^2+4k+1? Equivalently, can anyone > prove that you can't pack more than k^2 2-by-2 squares inside a > (2k+1)-by-(2k+1) square? > > Jim Propp > > On Friday, August 18, 2017, Allan Wechsler <acwacw(a)gmail.com> wrote: > > > Suppose you are asked to tile an integer square of side n with smaller > > squares, but the tiles are all of side 1, 2, or 3. What is the smallest > > number of tiles, a(n), that you can get away with? > > > > For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, > > 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct. > > > > If these values are right, then a(n) is not in OEIS. > > > > It's obvious that a(3k) = k^2. I would expect that big squares can be > > optimally tiled by filling most of the space with 3's, with a "fringe" of > > some sort around two sides if n is not a multiple of 3. But I maintain a > > small hope that there will be "weird" solutions that don't look like this. > > Can anybody provide more values? > > > ------------------------------ Subject: Digest Footer _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ------------------------------ End of math-fun Digest, Vol 174, Issue 38 *****************************************

1 0

Re: [math-fun] Is there a name for permutations that preserve no consecutive pairs?
by Dan Asimov 19 Aug '17

19 Aug '17

I was only checking for identical digraphs. But I hadn't thought to check for *sets* of two consecutive letters. I think cinematographer and megachiropteran have no identical digraphs, but they both have the consecutive pair {M,E} (if not others). —Dan >> Out[105]= {"ra"} --rwg Shouldn't that read "mc" ? Or have I misunderstood RWG notation ... WFL On 8/19/17, Dan Asimov <dasimov(a)earthlink.net> wrote: > Maybe the Daily Mail used "peninsulas" as a verb, but not to worry: > No newspaper would ever do that. >>From: Bill Gosper <billgosper(a)gmail.com> > >>On 2017-08-18 13:21, Dan Asimov wrote: >>> Don't know a name for this, other than "well-mixed anagrams". >>> >>> megachiropteran >>> cinematographer >>> >>> —Dan >>Or not. >>In[105]:= unshuf["megachiropteran", "cinematographer"] >> >>Out[105]= {"ra"} --rwg >>Gack. The Daily Mail just used peninsulas as a verb. >>> >>> >>> Bill Gosper wrote: >>> >>> ----- >>> I find them surprisingly tricky to eyeball correctly. >> >>Although I caught this one. --rwg >>> E.g., >>> unshuf[a_String, b_String] := >>> StringCases[a ~~ "¢" ~~ b, ___ ~~ x_ ~~ y_ ~~ ___ ~~ "¢" ~~ ___ ~~ x_ ~~ >>> y_ ~~ ___ :> x ~~ y] >>> >>> TableForm[{#, unshuf @@ #} & /@ {{"aniseed oils", >>> "loin disease"}, {"disanimate", "mediastina"}, {"pericleans", >>> "linespacer"}, {"scalyanteaters", >>> "transacetylase"}, {"laborintensive", "inventoriables"}, >>{"pleonastic", >>> "pointlaces"}, {"celeritous", >>> "reticulose"}, {"linesofcredit", "selfdirection"}, {"nitrosamines", >>> "nestorianism"}, {"crucible steel", "electric blues"}, {"blueshirt", >>> "thuribles"}, {"cornmeals", >>> "macrolens"}, {"cathartine", "anthracite"}, {"treelawns", >>> "waterlens"}, {"dipstream", "predatism"}}, >>> TableSpacing -> {1, 49}] >>> >>> aniseed oils >>> loin disease oi >>> >>> disanimate >>> mediastina di >>> >>> pericleans >>> linespacer er >>> >>> scalyanteaters >>> transacetylase an >>> >>> laborintensive >>> inventoriables ve >>> >>> pleonastic >>> pointlaces >>> >>> celeritous >>> reticulose >>> >>> linesofcredit >>> selfdirection di >>> >>> nitrosamines >>> nestorianism es >>> >>> crucible steel >>> electric blues el >>> >>> blueshirt >>> thuribles es >>> >>> cornmeals >>> macrolens >>> >>> cathartine >>> anthracite th >>> >>> treelawns >>> waterlens ns >>> >>> dipstream >>> predatism re >>> >>> redtapism >>> spermatid >>> >>> ammonolytic >>> commonality on >>> >>> partleading >>> plantigrade ad >>> >>> astonished >>> dositheans he >>> >>> alicesfern >>> craneflies es >>> >>> discrepate >>> pederastic >>> >>> forcertain >>> refraction >>> >>> camelspider >>> premedicals ls >>> >>> bestarred >>> redbreast ed >>> >>> apostlebird >>> pilotsbread

4 3

[math-fun] Mrs. Perkin's Quilt variation
by Allan Wechsler 19 Aug '17

19 Aug '17

Suppose you are asked to tile an integer square of side n with smaller squares, but the tiles are all of side 1, 2, or 3. What is the smallest number of tiles, a(n), that you can get away with? For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct. If these values are right, then a(n) is not in OEIS. It's obvious that a(3k) = k^2. I would expect that big squares can be optimally tiled by filling most of the space with 3's, with a "fringe" of some sort around two sides if n is not a multiple of 3. But I maintain a small hope that there will be "weird" solutions that don't look like this. Can anybody provide more values?

4 6

Re: [math-fun] Is there a name for permutations that preserve no consecutive pairs?
by Dan Asimov 18 Aug '17

18 Aug '17

Maybe the Daily Mail used "peninsulas" as a verb, but not to worry: No newspaper would ever do that. —Dan >From: Bill Gosper <billgosper(a)gmail.com> >On 2017-08-18 13:21, Dan Asimov wrote: >> Don't know a name for this, other than "well-mixed anagrams". >> >> megachiropteran >> cinematographer >> >> —Dan >Or not. >In[105]:= unshuf["megachiropteran", "cinematographer"] > >Out[105]= {"ra"} --rwg >Gack. The Daily Mail just used peninsulas as a verb. >> >> >> Bill Gosper wrote: >> >> ----- >> I find them surprisingly tricky to eyeball correctly. > >Although I caught this one. --rwg >> E.g., >> unshuf[a_String, b_String] := >> StringCases[a ~~ "¢" ~~ b, ___ ~~ x_ ~~ y_ ~~ ___ ~~ "¢" ~~ ___ ~~ x_ ~~ >> y_ ~~ ___ :> x ~~ y] >> >> TableForm[{#, unshuf @@ #} & /@ {{"aniseed oils", >> "loin disease"}, {"disanimate", "mediastina"}, {"pericleans", >> "linespacer"}, {"scalyanteaters", >> "transacetylase"}, {"laborintensive", "inventoriables"}, >{"pleonastic", >> "pointlaces"}, {"celeritous", >> "reticulose"}, {"linesofcredit", "selfdirection"}, {"nitrosamines", >> "nestorianism"}, {"crucible steel", "electric blues"}, {"blueshirt", >> "thuribles"}, {"cornmeals", >> "macrolens"}, {"cathartine", "anthracite"}, {"treelawns", >> "waterlens"}, {"dipstream", "predatism"}}, >> TableSpacing -> {1, 49}] >> >> aniseed oils >> loin disease oi >> >> disanimate >> mediastina di >> >> pericleans >> linespacer er >> >> scalyanteaters >> transacetylase an >> >> laborintensive >> inventoriables ve >> >> pleonastic >> pointlaces >> >> celeritous >> reticulose >> >> linesofcredit >> selfdirection di >> >> nitrosamines >> nestorianism es >> >> crucible steel >> electric blues el >> >> blueshirt >> thuribles es >> >> cornmeals >> macrolens >> >> cathartine >> anthracite th >> >> treelawns >> waterlens ns >> >> dipstream >> predatism re >> >> redtapism >> spermatid >> >> ammonolytic >> commonality on >> >> partleading >> plantigrade ad >> >> astonished >> dositheans he >> >> alicesfern >> craneflies es >> >> discrepate >> pederastic >> >> forcertain >> refraction >> >> camelspider >> premedicals ls >> >> bestarred >> redbreast ed >> >> apostlebird >> pilotsbread >> ----- >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1