# Odd Sequence (Algorithm?) **URL:** \ **Category:** Factual Questions\ **Created:** [July 18, 2006, 12:33pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996 "2006-07-18T12:33:35Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [July 18, 2006, 12:33pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/1 "2006-07-18T12:33:35Z")
I’ve got some code that calculates the following sequence: topID = 0 topID = 1 topID = 2 topID = 3 topID = 10 topID = 20 topID = 30 topID = 11 topID = 21 topID = 31 topID = 12 topID = 22 topID = 32 topID = 13 topID = 23 topID = 33 topID = 100 topID = 200 topID = 300 topID = 110 topID = 210 topID = 310 topID = 120 topID = 220 topID = 320 topID = 130 topID = 230 topID = 330 topID = 101 topID = 201 topID = 301 topID = 111 topID = 211 topID = 311 topID = 121 topID = 221 topID = 321 topID = 131 topID = 231 topID = 331 topID = 102 topID = 202 topID = 302 topID = 112 topID = 212 topID = 312 topID = 122 topID = 222 topID = 322 topID = 132 topID = 232 topID = 332 topID = 103 topID = 203 topID = 303 topID = 113 topID = 213 topID = 313 topID = 123 topID = 223 topID = 323 topID = 133 topID = 233 topID = 333 topID = 1000 topID = 2000 topID = 3000 topID = 1100 topID = 2100 topID = 3100 topID = 1200 topID = 2200 topID = 3200 topID = 1300 topID = 2300 topID = 3300 topID = 1010 topID = 2010 topID = 3010 topID = 1110 topID = 2110 topID = 3110 topID = 1210 topID = 2210 topID = 3210 topID = 1310 topID = 2310 topID = 3310 topID = 1020 topID = 2020 topID = 3020 topID = 1120 topID = 2120 topID = 3120 topID = 1220 topID = 2220 topID = 3220 topID = 1320 topID = 2320 topID = 3320 It is however pretty ugly code. Is this any sort of normal sequence and is there any short way of calculating it? I’m currently doing it all through adds, shifts, and binary operators. The sequence itself is essentially the mapping to a leaf in a tree. The above would be for a tree with four nodes at each branch and new branches/leaves are made based on the mapping. The goal is to have the mapping work in such a manner that any new leaf has all four slots filled before allocating memory for a new leaf. When all current-layer leaves are filled, one slot in one leaf is converted to a node pointer and the current item moved into the sub-leaf, ad infitum. Simply incrementing the key (i.e. 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, …) will work fine and keeps the tree of even-depth but means that up to almost four times the needed memory can be allocated, while as the above sequence causes there to be only +3 empty slots as worst case (assuming I have it right…) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 18, 2006, 1:26pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/2 "2006-07-18T13:26:42Z")
I’ve only given it a cursory scan, but it looks like you’re counting in ternary and writing the numbers right-to-left. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [July 18, 2006, 1:37pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/3 "2006-07-18T13:37:53Z")
[QUOTE=ultrafilter] I’ve only given it a cursory scan, but it looks like you’re counting in ternary and writing the numbers right-to-left. [/QUOTE] That was my first thought, but I’m not sure it’s that simple… ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 18, 2006, 1:42pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/4 "2006-07-18T13:42:14Z")
You’re right, it’s not exactly, but it’s pretty close (if you use base 4; after all, they don’t have the digit 3 in base 3). It really looks like counting in base 4 written right-to-left with 0x \> x. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [July 18, 2006, 1:59pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/5 "2006-07-18T13:59:06Z")
[QUOTE=ultrafilter] You’re right, it’s not exactly, but it’s pretty close (if you use base 4; after all, they don’t have the digit 3 in base 3). It really looks like counting in base 4 written right-to-left with 0x \> x. [/QUOTE] Can you explain what you mean by 0x \> x ? I still can’t see a proper sequence in there ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [July 18, 2006, 3:00pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/6 "2006-07-18T15:00:15Z")
It is essentially base 4 counting (though the real version of the code will be 32 or 64 base though it could be anything), but simply numbering left to right would be: 0 1 2 3 01 11 21 31 02 which is quite different from my sequence. That goes: 0 1 2 3 10 20 30 11 21 And I think what **ultrafilter** means by 0x \> x would be that 01 \> 1, 02 \> 2, and so on. Reversed order numbering. To try and show it as a tree a bit better: ```auto One leaf (top node) 00 01 02 03 One subleaf -->00 10 20 30 01 02 03 Two subleafs -->00 10 20 30 -->01 11 21 31 02 03 ``` With the above showing how the map goes to the proper place in the tree. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 18, 2006, 3:04pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/7 "2006-07-18T15:04:53Z")
hrmm… one way to do it for, is: ```auto List topIDList; for(int i = 1; i < 100; i++) List newTopIDList; for(int j = 1; j < 4; j++) foreach (int n in topIDList) String newTopIDString; sprintf("%d%0id, newTopIDString); newTopIDList.Add(int.Parse(newTopIDString)); topIDList.Append(newTopIDList); ``` the sprintf bit is a bit tricky, you would probably have to manually make the format string making liberal use of escape charecters. The algorithm basically works by noting that each larger length of strings is just a 1, 2 or 3 appended onto the previous strings. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 18, 2006, 3:08pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/8 "2006-07-18T15:08:31Z")
Uh, duhh… It would help if I included the arguments to the sprintf properly ```auto String newTopIDFormat = "\%d\%0" + i + "d"; //eg, for i = 4, it is "%d%04d sprintf(newTopIDString, newTopIDFormat, j, n); //So for j = 2, n = 23, it would be 20023 ``` ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [July 18, 2006, 3:13pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/9 "2006-07-18T15:13:56Z")
[QUOTE=Shalmanese] The algorithm basically works by noting that each larger length of strings is just a 1, 2 or 3 appended onto the previous strings. [/QUOTE] The mappings are bitmasks, but really the main problem with that method is that you would need to store every string you had ever created–and the structure is intended to hold up to the limit countable in a 32 or 64 bit value (so four billion or more.) ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [July 18, 2006, 6:46pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/10 "2006-07-18T18:46:13Z")
This is a reordered base-4 counting system. One way to describe it is: leading zeroes stripped, sorted primarily by length and then lexicographically on the reverse-ordered string. I’m not sure how helpful that is though. More helpful for counting with these numbers is that within a set of same-length keys, the first digit is counting base-3 (base-4 but skipping zero) and the remaining digits are normal base-4 counting, written least-significant-digit first. I’m not sure whether this code is any prettier than what you’ve got, but it’s quick anyway. ```auto typedef long KeyInt; // or long long, or whatever; digits are stored in 2-bit pairs of KeyInt struct key { KeyInt n; int l; }; void init( struct key *k ) { k->n = 0; k->l = 1; } void print( struct key* k ) { int i, n; for ( i = 0, n = k->n; i < k->l; ++i, n >>= 2 ) printf( "%d", n&3 ); } void inc( struct key *k ) { // increment low-order digit, base 3 k->n++; if ( !(k->n & 3) ) k->n++; // check for carry out; increment length if present KeyInt co = 1 << k->l*2; if ( k->n & co ) { k->n -= co; k->l++; } } int main( int argc, char** argv ) { int n; struct key K; init(&K); for ( n = 0; n < 100; ++n ) { printf( "%4d: ", n ); print(&K); printf( " " ); inc(&K); } } ``` It’s easy to get arbitrary elements of the sequence, too; you don’t have to increment if all you want is the nth element. But it sounds like you’re always using these in sequence, so that’s probably not important to you. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [July 18, 2006, 7:18pm UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/11 "2006-07-18T19:18:19Z")
Hm… I’ll need to look that over in the morning. Certainly smaller than what I had (and will probably be :smack:-inducing when I do.) ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 19, 2006, 4:22am UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/12 "2006-07-19T04:22:28Z")
[QUOTE=Sage Rat] The mappings are bitmasks, but really the main problem with that method is that you would need to store every string you had ever created–and the structure is intended to hold up to the limit countable in a 32 or 64 bit value (so four billion or more.) [/QUOTE] Ok, so the one that doesn’t require you to store the results would be: ```auto int nextTopID (int curTopID) return int.Parse(_nextTopID(cur.ToString()); String _nextTopID(String curTopIDStr) { foreach (char c in curTopIDStr) if (c != 3) //check if we overflow to the next digit break; return "1" + "0".repeat(curTopIDStr.Length); if(curTopIDStr[0] == "3") return ("1" + nextTopID(curTopIDStr[1..]); else curTopIDStr[0]++; return curTopIDStr; } ``` curTopIDStr[1..] means take the substring from 1 to the end. Just assume the language does automatic casting between strings and ints. I know no language does but it makes the code clearer. Theres a bit of subtlety to the string formatting in that you need to preserve leading zeros though when you convert nextTopID back into and int. It’s the same basic principle as the earlier one only made recursive rather than using dynamic programming. It has to manually compute the next increment rather than pulling it from a precomputed array. ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [July 19, 2006, 5:04am UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/13 "2006-07-19T05:04:13Z")
[QUOTE=Shalmanese] Ok, so the one that doesn’t require you to store the results would be: _[code snipped…]_ curTopIDStr[1..] means take the substring from 1 to the end. Just assume the language does automatic casting between strings and ints. I know no language does but it makes the code clearer. Theres a bit of subtlety to the string formatting in that you need to preserve leading zeros though when you convert nextTopID back into and int. It’s the same basic principle as the earlier one only made recursive rather than using dynamic programming. It has to manually compute the next increment rather than pulling it from a precomputed array. [/QUOTE] I’m not sure I understand the notation you’re using; but given an input of 330, won’t this return 111 instead of 101? \_nextTopID(“330”) -\> “1” + \_nextTopID(“30”) -\> “1”+“1”+\_nextTopID(“0”) -\> “1”+“1”+“1” = “111”. In the OP, the first digit behaves differently from the rest. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 19, 2006, 5:21am UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/14 "2006-07-19T05:21:41Z")
[QUOTE=Omphaloskeptic] I’m not sure I understand the notation you’re using; but given an input of 330, won’t this return 111 instead of 101? \_nextTopID(“330”) -\> “1” + \_nextTopID(“30”) -\> “1”+“1”+\_nextTopID(“0”) -\> “1”+“1”+“1” = “111”. In the OP, the first digit behaves differently from the rest. [/QUOTE] Ah good point. You would have to write a special case for the first digit. I missed that. ```auto int nextTopID (int curTopID) return int.Parse(_nextTopID(cur.ToString(), true); String _nextTopID(String curTopIDStr, boolean isFirstDigit) { foreach (char c in curTopIDStr) if (c != 3) //check if we overflow to the next digit break; return "1" + "0".repeat(curTopIDStr.Length); if(curTopIDStr[0] == "3") if(isFirstDigit) return ("1" + nextTopID(curTopIDStr[1..], false); else return ("0" + nextTopID(curTopIDStr[1..], false); else curTopIDStr[0]++; return curTopIDStr; } ``` ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [July 19, 2006, 5:49am UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/15 "2006-07-19T05:49:30Z")
The first thing I notice is that this is not a true list of the permutations of 4 elements since the first digit is never 0 (forget the first number). Patterns I noticed (N.B. start counting at n=0) 1 digit: n = 1 to 3 2 digits: n = 4 to 15 3 digits: n = 16 to 63 … x digits: n = 4^(x-1) to (4^x)-1 The second pattern is the digits themselves. The leading digits are in blocks of 1 (123), the second digits are in groups of 3 (000111222333), the third digits are in groups of 12 (000000000000111111111111222…). Examining the first pattern we see why. Look at the group of 2 digit numbers - there are 12 of them. Divided up into 4 elements we get 12/4 or groups of 3. Look at the group of 3 digit numbers - there are 48 of them. Divided up into 4 elements we get 48/4 or groups of 12. Putting all of this together, I think your best bet is to contruct the result digit by digit. Let’s say you want the Nth number (bigger than 0 of course). First of all, figure how many digits it will have [1 + trunc(log4 (N))] This would give you your loop parameters. First digit = N mod 3 (here you have to cheat since it will return the pattern 120. Put in a boolean check like IF a=0 THEN a:=3;) Second digit = ((N-4) DIV 3) MOD 4 Third digit = ((N-16) DIV 12) MOD 4 Fourth digit = ((N-64) DIV 48) MOD 4 … Xth digit = ((N-(4^(X-1))) DIV ((4^(X-2))\*3) MOD 4 If you need the value of the number, it would be easy to reconstruct from the digits. Since the number is created working left to right but place value is read right to left, I would recommend using a stack to store the digits then calculate the value of the number. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [July 19, 2006, 7:50am UTC](https://boards.straightdope.com/t/odd-sequence-algorithm/364996/16 "2006-07-19T07:50:20Z")
[QUOTE=Omphaloskeptic] This is a reordered base-4 counting system. One way to describe it is: leading zeroes stripped, sorted primarily by length and then lexicographically on the reverse-ordered string. I’m not sure how helpful that is though. More helpful for counting with these numbers is that within a set of same-length keys, the first digit is counting base-3 (base-4 but skipping zero) and the remaining digits are normal base-4 counting, written least-significant-digit first. I’m not sure whether this code is any prettier than what you’ve got, but it’s quick anyway. [/QUOTE] Had a chance to look at it now, and yeah… just keeping the digits in reverse order is a good bit easier (though of course this requires flipping them back around for use.) Probably this is what I’ll do. My current code is essentially doing the same thing, just manually carrying the overflow over the “wrong” way.