A "Magic" Sequence

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

This program will generate "Magic Sequences".  .A Magic Sequence of length N has the property that each value in the series represents the number of times that its rank (position number) relative to zero, appears in the sequence. If the elements are represented by Xi, 0<=i<=N-1 then Xi = the number of occurrences of "i" in the sequence.

So for sequences of length 5, one (and only) example is [2,1,2,0,0], magic because x0 = 2 and there are 2 zeroes in the sequence; X1=1 and there is only a single 1 in the sequence; x2=2 and there are two "2"s, X3=X4=0 and there are no "3"s or "4"s.

Background & Techniques

A viewer wrote recently asking about a program to generate "Magic Sequences". He included code that calculated the sequence of length 7 by nesting loops 7 levels deep, each level generating a digit position.  Clearly he felt that there must be a better.  Probably so. 

There does not seem to be much literature on sequences with this property and they appear to degenerate into a predictable pattern rather soon so are perhaps not so interesting from a mathematical standpoint but did make a good programming exercise.

I generalized the code to produce three additional ways to calculate sequences for a given N. Each method is faster than the preceding version.

Method 1 simply counts in base N and checks each to see if it is "magic". [00001, 00002, 00003, 00004, 00010 ,..., 21200, ..., 44444, 44445] for N=5, for example.

The next two methods take advantage of the fact that the sum of the non-zero elements of a sequence form an partition of N. (Each value in the sequence represents the count of a particular value and there are N of these values
altogether, so the sum must equal N.) So we might as well start with the integer partitions of N.

Method 2 generates integer partitions of N, checks that one of the values equals the number of zeros in the sequence and then expands the sequence with zeros and permutes the last N-1 digits looking for magic sequences. For N=7, the partition {1,1,2,3} is a potential solution since it contains 4 numbers so there must be 3 zeros in the sequence and we have a 3 in the partition that can occupy the 1st position.    Method 2 then permutes the remaining 6 sequence members, {1,1,2,0,0,0}, checking for than would complete a valid magic sequence.   This requires checking 6!=720 possibilities.

Method 3 improves on Method 2 by permuting the potential position where the digits of each partition might appear in the sequence.  so in the N=7  case,  we  only check the number of places that {2,1,1} can be inserted into the last 6 positions.  This requires that only  (6!/3!)=6*5*4=120 patterns be checked. 

Notes for programmers

bulletFrom the programming perspective, our TIntPartition class in unit UIntPartition2 and TComboset class in the UComboV2 library unit  makes generating the partitions and permutations quite easy.   Each of these units initializes a default instance of the class (DefPartition for TIntpartition and  Combos for TComboSet) which avoids creating our own.
bulletThere is a commented version of a procedure for Method 1 (Button1Click) which  works as literally described above, counting in base N.   The equivalent, but faster, procedure actually used is a version of the TComboset  NextLexRepRPermute function which generates permutations with repeats.  For permuting N of N items, this is equivalent to counting in Base N.  
bulletRun times for each method are displayed, making the it easy to determine the effect of changes on speed.

 

Running/Exploring the Program 

bullet Download source
bullet Download  executable

Suggestions for Further Explorations

Other enhancements to increase speed?

For the math types, it appears that for N>6, there is only a single sequence with four non-zero members and they are: X0=N-4,  X1=2,  X2=1 and XN-4=1.  How about proving this?

 

Original Date: May 1, 2007 

Modified: July 29, 2017

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.