wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> What's this sequence?
        
(Message started by: Quetzycoatl on Dec 22nd, 2003, 1:40pm)
Title: What's this sequence?
Post by Quetzycoatl on Dec 22nd, 2003, 1:40pm
9, 81, 18, 81, 9, 702, 9, 171, 27....?

1) what are the next few terms of this sequence?
2) what does this sequence describe?
3) can you write a formula to predict elements of this sequence?


-Quetzycoatl
Title: Re: What's this series?
Post by Icarus on Dec 22nd, 2003, 3:52pm
One thing to note is that all the elements are divisible by 9. Dividing gives

1, 9, 2, 9, 1, 78, 1, 19, 3, ...

I don't recognize a pattern in this immediately either, though.

By the way, this is a "sequence", not a "series". A series would be 9+81+18+81+9+702+9+171+27+...
Title: Re: What's this series?
Post by Quetzycoatl on Dec 22nd, 2003, 4:38pm
Thanks for clarifying the difference between a sequence and series for me, I couldnt remember. There are a few interesting aspects to this sequence. By the way I only know the answer to the first two questions, I am not sure the third is possible, but I would love to see it if it is. I happened upon this sort of by accident and have not been able to find anything about it. I'm including a hint below:

HINT:  [hide] I noticed this sequence while trying to write a little program to come up with anagrams. [/hide]

P.S. Sorry about the dual posting, won't do it again.

-Quetzycoatl
Title: Re: What's this sequence?
Post by Quetzycoatl on Dec 26th, 2003, 12:55pm
Since no-one seems to be very interested in my problem, and because I am really only interested in an answer to #3 I am going to give the answers to the first two questions below.

Someone who, unlike me, actually knows some math, please look at this!

[hide]

1)  9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9, 5913, 9, 81, 18, 81, 9, 1602, 9, 261, 36, 63, 27, 594, 18, 162, 36, 162, 18, 603, 9, 171, 27, 72, 18, 5814, 9, 171, 27, 72, 18, 603, 9, 261, 36, 63, 27, 1584, 27, 63, 36, 261, 9, 603, 18, 72, 27, 171, 9, 5814, 18, 72, 27, 171, 9, 603, 18, 162, 36, 162, 18, 594, 27, 63, 36, 261, 9, 1602, 9, 81, 18, 81, 9, 5913, 9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9….

2) Choose a number of digits between 1 and 9 and write the lowest number you can using each digit only once. So for 5 it would be 12345 (we are excluding 0). Now find the next highest number using those same digits, 12354, an increase of 9. The next highest is 12435, an increase of 81 etc.
   The above set shows all 120 increases for 5 digits, the first 24 places are the same as the set for 4 digits, the first 6 are the same as 3 digits etc.
   Each set is palindromic.
   All terms are factors of nine.
   Within the 5 digit set the 2 digit set (9) repeats 24 times (the number of terms in the 4 digit set), the three digit set repeats 6 times, and the four digit set repeats twice.

   One other really wierd thing:
for three digits the permutations look like this
123
132
213
231
312
321

their sum is 1332.

the terms of the 3 digit sequence are:
9
81
18
81
9

which adds up to 198.

add 198 to the first 3 digits of Pi, then the next three and once more to the next three:

 198    198    198
+314  +159   +265
____  ____   ____
512     357     463

add those three sums together and you get 1332!

This seems to me like a wierd coincidence and I have not been able to translate it anything other than 3 digits, but who knows maybe their is something to it.


[/hide]

-Quetzycoatl
Title: Re: What's this sequence?
Post by THUDandBLUNDER on Dec 27th, 2003, 2:17am

Quote:
Since no-one seems to be very interested in my problem,

Hi Quetzycoatl. I don't think it's the case that nobody is interested.
More like nobody could figure out your sequence.


Quote:
The above set shows all 120 increases for 5 digits, the first 24 places are the same as the set for 4 digits, the first 6 are the same as 3 digits etc.

120 = 5!
24 = 4!
6 = 3!
etc.


Quote:
Each set is palindromic.

That figures.


Quote:
All terms are factors of nine.
 
Using an arbitrary base b they will all be multiples (not factors) of b-1


Quote:
Within the 5 digit set the 2 digit set (9) repeats 24 times (the number of terms in the 4 digit set), the three digit set repeats 6 times, and the four digit set repeats twice.
 
Seems like within an n-digit set the m-digit set will occur (n-m+1)! times. (m =< n)
   
Concerning your connection with Pi, let the 3 digits be a, a+1, and a+2
Adding the 6 permutated numbers, we get 666(a + 1) which equals 1332 when a = 1
And 1332 - (3*198) = 738 = 314 + 159  + 265
But I don't think there's anything surprising here.

If we use an arbitrary number base (b > 6), instead of 666(a+1) we get 6(a + 1)(b2 + b + 1)
And instead of 198 we get 2(b2 - 1)
Hence 1332 - (3*198) becomes 6(a + 1)(b2 + b + 1) - 6(b2 - 1) = 6[ab2 + (a + 1)b + (a + 2)]
And putting a = 1 this becomes 6(b2 + 2b + 3)
This equals your magic 738 (or 6*123) only when b = 10.
Title: Re: What's this sequence?
Post by Quetzycoatl on Dec 29th, 2003, 6:48am
Thanks Thud, any thoughts about whether a formula is possible?
Title: Re: What's this sequence?
Post by THUDandBLUNDER on Dec 30th, 2003, 12:42pm

Quote:
Thanks Thud, any thoughts about whether a formula is possible?

Well, I have a formula but.......it's longer than the sequence.  :D
Title: Re: What's this sequence?
Post by Barukh on Jan 1st, 2004, 2:40am

on 12/29/03 at 06:48:03, Quetzycoatl wrote:
Thanks Thud, any thoughts about whether a formula is possible?

I doubt there’s a closed formula (although THUD&BLUNDER claim he’s got one :P). However, that doesn’t mean the situation is hopeless: we still can compute the M-th element of the sequence (quite) efficiently for any given M.

Quetzycoatl, what you start with, is a sequence of permutations of numbers {1, …, n} in so called lexicographic order, and then build a sequence of differences of adjacent elements. Thus, we need a procedure for producing the M-th permutation in lexicographic order without actually generating all the permutations. The procedure I’m going to describe, is based on the following observation: for any M, it is easy to determine the first number in M-th permutation: just divide (M-1) by (n-1)!, and add 1.

1). Find n-1 numbers d1, …, dn-1 such that
d11! + d12! + … + dn-1(n-1)! = M – 1.
To make this, observe that the left side may be written as d1 + 2(d2 + 3(d3+…)), so d1 = (M-1) mod 2, d2 = [smiley=lfloor.gif](M-1)/2[smiley=rfloor.gif] mod 3 etc., just like in usual conversion of number into arbitrary base b.

2). Arrange the numbers 1, …, n as a list in that order, and perform n-1 iterations as follows: at the j-th iteration, take the (dn-j+1)-th element in the not-yet processed list, and push it to the end of the already-processed list (which is initially empty). The resulting list will be the sought permutation.

The attached figure shows the example for n = 5, M = 77. For that, we get (d1 d2 d3 d4) = (0 2 0 3). The white boxes are the not-yet processed elements, while the yellow boxes are already processed. At every iteration, the chosen elements are highlighted. Thus, the 77-th smallest number formed by five digits is 41523.
Title: Re: What's this sequence?
Post by Quetzycoatl on Jan 5th, 2004, 8:28am
Barukh,
I think I understand the process you describe, but just to clarify:
dn= [lfloor](m-1)/x[rfloor] mod (n+1)
where x is 1 if n is odd and 2 if n is even?

perhaps I am doing something wrong but I don't think this works. I was able to replicate your example which came out correctly but I tried a few more values for m and n and most of them were wrong.

for example if m = 13 and n = 4 I come up with 1234, which is clearly wrong since it is the same as m = 1 n = 4.

In fact, for n = 5 I only get correct results on m = 1, 34, 44, 77, 87 and 120.

for n = 4 it only works where m = 1, 5, 10, 15, 20 and 24.

All results are correct for n = 3 and 2.
Title: Re: What's this sequence?
Post by Barukh on Jan 6th, 2004, 12:53am

on 01/05/04 at 08:28:06, Quetzycoatl wrote:
I think I understand the process you describe, but just to clarify: dn= [lfloor](m-1)/x[rfloor] mod (n+1) where x is 1 if n is odd and 2 if n is even?

No, that’s not correct. Sorry for not describing it precisely… To understand the process better, think about the conversion of a decimal number to the binary form: at every iteration, you compute the modulo 2 of the number (to get the next digit), and also divide the number by 2 (to work with a new number at the next iteration). Here’s the pseudocode of the procedure to compute the d’s:
q1 = M-1
for j = 1 ... n-1
{
  dj = qj mod (j+1)
  qj+1 = [smiley=lfloor.gif] qj/(j+1) [smiley=rfloor.gif]
}

Quote:
…for example if m = 13 and n = 4 I come up with 1234, which is clearly wrong since it is the same as m = 1 n = 4.
For this particular example, the above procedure gives (d1 d2 d3) = (0 0 2), and the answer is 3124, which is correct.
Title: Re: What's this sequence?
Post by Quetzycoatl on Jan 6th, 2004, 8:01am
Actually you did make the comparison to binary conversion before and I just failed to notice. Thanks for clarifying It seems to work great!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board