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

Re: [math-fun] A few self-descriptive fractal sequences
by dasimov＠earthlink.net 04 Dec '05

04 Dec '05

Kerry, You've said some interesting things about fractal sequences, like how to detect them. But what is their underlying definition? Thanks, Dan

3 2

Re: [math-fun] A few self-descriptive fractal sequences
by Kerry Mitchell 04 Dec '05

04 Dec '05

Here are a few more self-descriptive fractal sequences. "Upper trimming" is another technique for determining if a sequence is a fractal sequence, if the sequence contains all positive integers. The first occurrence of each integer is deleted from the sequence. If the resulting sequence is the same is the original, then it is a fractal sequence. This is an example of a fractal sequence: 1, 1, 2, 1, 3, 4, 2, 5, 1, 6, 7, 8, 3, 9, 10, 11, 12, 4, 13, 14, 2, ... If we denote the first occurrence of each integer by X, we get: X, 1, X, 1, X, X, 2, X, 1, X, X, X, 3, X, X, X, X, 4, X, X, 2, ... and dropping the Xs: 1, 1, 2, 1, 3, 4, 2, ... Which is the beginning of the original sequence. This sequence is also self-descriptive, in that each element gives the number of Xs (first occurrences of integers) that were removed just before it. Here are the first 200 terms: 1, 1, 2, 1, 3, 4, 2, 5, 1, 6, 7, 8, 3, 9, 10, 11, 12, 4, 13, 14, 2, 15, 16, 17, 18, 19, 5, 20, 1, 21, 22, 23, 24, 25, 26, 6, 27, 28, 29, 30, 31, 32, 33, 7, 34, 35, 36, 37, 38, 39, 40, 41, 8, 42, 43, 44, 3, 45, 46, 47, 48, 49, 50, 51, 52, 53, 9, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 10, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 11, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 12, 87, 88, 89, 90, 4, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 13, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 14, 118, 119, 2, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 15, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 16, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 17, 168, 169, 170, 171, 172, 173, 174, 175, 176 Here's another one: 1, 1, 2, 1, 3, 2, 1, 4, 3, 5, 2, 1, 4, 6, 3, 5, 7, 2, 8, 1, 4, 6, 3, 9, 5, 7, 2, 10, ... This sequence gives the number of numbers that are retained between Xs that are dropped. Alternatively, each element is the number of numbers between two first occurrences of integers. For example, the first 3 above describes the three numbers 2, 1, 4 between the first 5 and the first 6. Here are the first 200 terms: 1, 1, 2, 1, 3, 2, 1, 4, 3, 5, 2, 1, 4, 6, 3, 5, 7, 2, 8, 1, 4, 6, 3, 9, 5, 7, 2, 10, 8, 1, 4, 6, 3, 11, 9, 5, 12, 7, 13, 2, 10, 8, 1, 14, 4, 6, 3, 11, 9, 5, 15, 12, 7, 13, 16, 2, 10, 8, 1, 14, 17, 4, 6, 3, 11, 9, 5, 15, 18, 12, 7, 19, 13, 16, 2, 10, 8, 1, 14, 17, 20, 4, 21, 6, 3, 11, 9, 22, 5, 15, 18, 12, 7, 19, 23, 13, 16, 2, 24, 10, 8, 1, 14, 17, 20, 4, 21, 6, 25, 3, 11, 9, 22, 5, 26, 15, 18, 12, 7, 19, 23, 13, 27, 16, 2, 28, 24, 10, 8, 1, 14, 17, 20, 4, 21, 6, 29, 25, 3, 11, 9, 22, 5, 26, 15, 30, 18, 31, 12, 7, 19, 23, 32, 13, 27, 16, 2, 28, 24, 33, 10, 8, 1, 34, 14, 17, 20, 4, 21, 6, 29, 25, 3, 11, 9, 35, 22, 5, 26, 15, 30, 18, 31, 12, 7, 36, 19, 23, 32, 13, 27, 37, 16, 2, 28, 24, 33, 10, 8, 1 This last fractal sequence describes the number of Xs that are dropped and the number of numbers written between dropped Xs: 1, 1, 2, 1, 3, 4, 2, 1, 5, 3, 6, 7, 8, 4, 2, 1, 9, 10, 11, 12, 5, 3, 6, 7, 13, 14, 8, 4, 15, 2, 16, 17, 18, 19, 20, 1, 9, 10, 11, 12, 21, 22, 23, 5, 3, 6, 24, 25, 26, 27, 28, 29, 7, 13, 14, 8, 4, 15, 30, 31, 32, 33, 34, 35, 36, 2, 16, 17, 18, 19, 20, 1, 37, 38, 39, 40, 41, 42, 43, 44, 9, 10, 11, 12, 21, 22, 23, 5, 45, 46, 47, 48, 3, 6, 24, 25, 49, 50, 26, 27, 51, 28, 52, 53, 54, 55, 56, 57, 58, 59, 60, 29, 7, 13, 14, 8, 4, 15, 30, 31, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 32, 33, 34, 35, 36, 2, 16, 17, 18, 19, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 20, 1, 37, 38, 39, 40, 41, 42, 43, 44, 9, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 10, 11, 12, 21, 22, 23, 5, 45, 46, 47, 48, 3, 94, 95, 96, 97, 98, 6, 24, 25, 49, 50, 99, 100, 101, 26 Kerry

1 0

[math-fun] Dick Howell
by Schroeppel, Richard 04 Dec '05

04 Dec '05

(Apologies to the non-MIT folks here, but for historical reasons we have a lot of MIT PDP1 & AILab people.) The MIT Class Notes (nominally part of Tech Review, but nowadays it's email) reports that Richard Howell '68 died in August. Class Notes says they have no other information. Dick Howell was part of the PDP1 crowd ~1965-70. I remember he wrote a Conway Life program for the PDP1, and an early chess program. Rich rcs(a)cs.arizona.edu

2 1

[math-fun] A few self-descriptive fractal sequences
by Kerry Mitchell 03 Dec '05

03 Dec '05

"Lower trimming" is one technique for determining if a sequence is a fractal sequence. 1 is subtracted from each element, and all the zeroes are thrown away. If the resulting sequence is the same is the original, then it is a fractal sequence. This is an example of a fractal sequence: 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 4, 1, 2, 1, 1, 3, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, ... If we subtract 1 from each element, we get: 0, 1, 0, 0, 2, 0, 1, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 0, 0, ... and removing all the zeroes leaves us with: 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, ... Which is the beginning of the original sequence. This sequence is also self-descriptive, in that each element gives the number of zeroes that were removed before it. And, for reasons I haven't figured out, the indices where the sequence hits a new maximum value (2 at the 2nd position, 3 at the 5th position, 4 at the 13th, 5 at the 34th, etc.) are every second Fibonacci number. Here's another one: 1, 2, 1, 3, 2, 1, 4, 1, 3, 2, 5, 1, 2, 4, 1, 3, 1, 6, 2, 3, 5, 1, 2, 1, 4, 2, 7, 1, 3, 4, 1, 6, ... This sequence gives the number of numbers that are retained between zeroes that are dropped. Alternatively, each element is the number of numbers between 1's in the original sequence. This last fractal sequence combines both ideas. 1, 2, 1, 1, 3, 2, 1, 2, 1, 4, 1, 1, 1, 3, 2, 3, 1, 1, 2, 5, 1, 2, 1, 1, 2, 2, 1, 4, 1, 1, 1, 1, ... Each element gives the number of zeroes dropped before it and the number of elements written before the next zero. Nothing too terribly earth-shaking, but enough to keep me occupied on a Saturday night. :-) Kerry

1 0

[math-fun] Periodic Antisymmetric Matrices counted by Hermitte Numbers
by wouter meeussen 03 Dec '05

03 Dec '05

Antisymmetric: Transpose(A)= -A, so zero diagonals Periodic: some matrix power = Identity Matrix A067994= Hermitte Numbers= 1,0,2,0,12,0,120,0,1680, ... Their periods are all 4. Strong law of small numbers checked upto n=8. Who says this is self-evident? W.

1 0

[math-fun] Algorithm for counting nonisomorphic colorings
by David Wilson 03 Dec '05

03 Dec '05

Tsvetelina Petkova has asked for my help with a program to count nonisomorphic colorings of general graphs. I haven't made any promises. I can describe an algorithm for doing this, however, it would be a bear to program in Perl or C++, which are all I have at my disposal. I was wondering if someone versed in Mma or some other symbolic language might want to discuss the possibility of implementing my algorithm. -------------------------------- - David Wilson

1 0

RE: [math-fun] New sequences; comments on old; origin of problem?
by dasimov＠earthlink.net 01 Dec '05

01 Dec '05

Richard Guy writes many cheerful facts about the square of n by n dots: << Given a square n by n array of dots, what is the maximum number of edges in a convex polygon whose vertices are members of the array? >> As usual, I wonder about the same question applied, instead of to the n by n array of dots, to the n by n "discrete square torus" array of dots. I.e., if all addition is mod n, then each point (K,L) of Z/nZ x Z/nZ is connectable to (K+d, L+e) where (d,e) lies in the set {-1,0,1} x {-1,0,1} - {0,0}. Another related question is to use the "discrete rhombic torus", also describable as the points Z/nZ x Z/nZ, but with the point (K,L) connectable to (K+d,L+e) only for (d,e) in {-1,0,1}x{-1,0,1} - {(-1,-1),(0,0),(1,1)} (again, addition is mod n). --Dan

1 0

[math-fun] Re: New sequences; comments on old; origin of problem?
by Richard Guy 30 Nov '05

30 Nov '05

Yes, I confused Derek with one of the students. He is in fact one of the helpers! There's only one, as far as I know. R. On Wed, 30 Nov 2005, Jim Nastos wrote: > On 11/30/05, Richard Guy <rkg(a)cpsc.ucalgary.ca> wrote: >> >> Derek Kisman, a high school student who is >> one of a group we're training for the Olympiad, >> has recently produced a complete and elegant >> solution to the following problem. > > Hi Professor Guy, > > Is this it a coincidence or a mislabeling that Derek Kisman is a high > school > math Olympian? (Or perhaps outdated.) > I did my undergraduate with Derek Kisman at Waterloo, and he was a silver > medalist at the 1996 Olympiad. He graduated in 2000, named Putnam fellow > in 1999. Perhaps he is helping with Olympiad training, instead of being a > part of > the group being trained? Or perhaps there is a second Derek Kisman? :) > > Thanks, > Jim Nastos

1 0

[math-fun] New sequences; comments on old; origin of problem?
by Richard Guy 30 Nov '05

30 Nov '05

I'll also copy this to the editors, in the hope that someone will get it into proper OEIS shape, and even check the hand calculation and copying. But I'd be glad to hear from anyone who can locate the problem. R. Derek Kisman, a high school student who is one of a group we're training for the Olympiad, has recently produced a complete and elegant solution to the following problem. Given a square n by n array of dots, what is the maximum number of edges in a convex polygon whose vertices are members of the array? Here is the first not-immediately-obvious case, n = 5: . o o . . o . . o . o . . . . . o . . o . . . o o Can anyone locate where I got the problem from? I read it somewhere in the case n = 2004, so it was presumably used in, or suggested for, some Olympiad competition (possibly a British one) last year. I seem to recall it was quoted in an article about problems in general. Define the cost c of an edge joining x1 y1 to x2 y2 to be the Manhattan metric |x2 - x1| + |y2 - y1| so that the total cost of a polygon is at most 4(n - 1) Optimal solutions contain 4k edges chosen with minimal cost 1 2 3 4 5 6 7 c = 1 2 3 3 4 4 5 5 5 5 6 6 7 7 7 7 7 7 ... where each value of c appears phi(c) times. This is A038567, though its connexion with this problem isn't mentioned. The cumulative sum of this sequence, 1 3 6 9 13 17 22 27 32 37 43 49 56 63 ... agrees with A002815 as far as 56 63 70 77 but then continues 85 93 102 111 ... instead of 70 77 84 91 99 107 115 123 132 141 150 159 168 177 187 197 207 217 228 239 250 261 272 283 294 305 316 327 339 351 363 375 388 401 414 427 440 453 466 479 492 505 518 531 545 559 573 587 601 615 630 645 660 so this is a new sequence. The corresponding values of n are one larger than these, namely 2 4 7 10 14 18 23 28 33 38 44 50 57 64 71 78 85 92 100 108 116 124 133 142 151 169 178 188 198 208 229 240 251 262 273 284 295 306 317 328 340 352 364 376 389 402 415 428 441 454 467 480 493 506 519 532 546 560 574 588 602 616 631 646 661 676 691 706 721 726 742 and these are not in OEIS. Important subsequences of these two sequences are obtained by accumulating c * phi(c). phi(c) is A000010, a very early specimen. c * phi(c) is A002618, where it is described as phi(n^2) -- perhaps the alternative form should be given and maybe the connexion with the present problem. The accumulation 1 3 9 17 37 49 91 123 177 217 ... is A011755. Should we mention the connexion with this problem? The corresponding values of n are one larger, and don't appear in OEIS: 2 4 10 18 38 50 92 124 178 218 328 376 532 616 736 864 1136 1244 1586 1746 1998 2218 2724 2916 3416 3728 4214 4550 5362 5602 6532 7044 7704 8248 9088 9520 10852 11536 12472 13112 14752 ... [Derek Kisman calculated as far as 1998 and was able to obtain the answer, 561 for n = 2004, to the original problem] So here is the real sequence: max no of edges in a convex polygon on an n by n grid: n = 0 1 2 3 4 5 6 7 8 9 10 0? 1? 4 6 8 9 10 12 13 14 16 11 12 13 14 15 16 17 18 19 20 16 17 18 20 20 21 22 24 24 25 21 22 23 24 25 26 27 28 29 30 26 27 28 28 29 30 31 32 32 33 31 32 33 34 35 36 37 38 39 40 34 35 36 36 37 38 38 40 40 41 41 42 43 44 45 46 47 48 49 50 41 42 43 44 44 44 45 46 47 48 48 48 More terms can be calculated for a reasonable fee, but we don't have a slick way of getting them. But there probably aren't any more which are as hard as showing that 45 edges can't be attained for n = 46. I'll write this up and send a copy to anyone who's interested. Best to all, R.

1 0

RE: [math-fun] Re: Query
by Eric Angelini 30 Nov '05

30 Nov '05

> clinically insane ... Those words are mine -- I've bought them from AdWords to redirect customers towards my website. You ow me half a cent, Joerg. Best, É.

2 1