Recurrence algorithms, logarithmic series etc

@skipper-wJtaxo • Oct 14, 2024

Oct 14, 2024

1.2K

Is there anyone here good at finding recurrence formulas in algorithm design? Or with a good grasp of a logarithmic series like: a[sub]n[/sub] = a[sub]n-1[/sub] + a[sub]n-2[/sub]?

Like how a Fibonacci series is computed from the sum of two preceding terms, etc?

The series is a power series inside a "commutative algebraic form", the simplest of which is the ratio 3/2 (a sesquiplicate ratio). The interesting thing is that this is the inverse of the fraction used in Turing-computable numbers (which is a number that has an integer representation that can be written as a signed-exponent decimal fraction).

The series I'm trying to find a recursion for is:

1 9 54 321 1,847 9,992 50,136 227,536 870,072 1,887,748 623,800 2,644 3,674,160

The last number is a summed total of all the numbers to its left, sorta like the equation, but with 12 a[sub]n[/sub] terms, rather than 2, so there is a second inner sequence that the rightmost total adds together, in a; the inner sequence is b, say.
I mean, all logarithmic forms come down to a base of numbers, ultimately log2 is the last "useful" base....
->??

The "brute force" approach is to subtract the leftmost number from the total, factor the new total and so on, look for say, large primes you can factor into terms that divide a remainder....

Like 0 Replies 9

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

skipper

@skipper-wJtaxo • Jan 24, 2010

This is another sequence that adds to the same total.

1 6 27 120 534 2,256 8,969 33,058 114,149 360,508 930,588 1,350,652

The "13th" number is also the 12th figure, once you subtract 1 from it and make 1 the zeroth figure.
Or, you just state that the leftmost is the zeroth place for a figure in 12 places. Subtracting 1 from T is equivalent to sending the zeroth figure (a point) to mathematical infinity. So is declaring zeroth place for an element or character, in list-based programming this is a set with _ in it, for instance, an "rth figure".

So the series has two forms, the sums together are equal to 2T, and you initially have T - 1, and 1/T, and an equal number of places, but unequal figures in each that, if you interpret as integer values add to the same total.
0
Hussanal Faroke

@hussanal-faroke-U5nNM8 • Jan 25, 2010

I don't get actually how u create the second series, i will try if u explain that!
0
skipper

@skipper-wJtaxo • Jan 25, 2010

Ok both series are what "falls out" of the Pocket Cube.
The second is formed by using only quarter turns (QTM), and the first is formed using full turns (which means FTM includes QTM).
So the first series includes the second, both add to identical integer totals, so if the first is TA, the second TB, the series are respectively Ta and Tb, where a and b are indexed by their place, n, which goes from a zeroth, to a 11th place. Write n as 111111111111, the number of places, rewrite a decimal point in front as i and a 0 at the end for a terminator. Then there is a sequence which is computable, of the characters c[sub]n[/sub], in Turing notation you substitute r for n, and use a constant fraction (2/3)[sup]r[/sup], for the rth figure (character, symbol, token, ...).

In other words, you also write ,3674160 (in binary), preceded by a preamble that tells an interpreter "this is a real number, that can be rewritten as an integer, by shifting it n places"

And the attack strategy here is that I also have a third series, for the original cube, which is incomplete. This consists of a set of recurrences that enumerate subtotals for n, or an nth figure "in place". These equations must include the above sequences, since they are also computable Turing-wise, like writing out a number in n places and each place has a figure which is a subtotal. The problem is the ratio in the cube (3/2) vs in the Turing-recursive formula (2/3), and swapping n for r properly.
0
skipper

@skipper-wJtaxo • Jan 25, 2010

Oops, the second sequence isn't complete, I missed some terms at the end:

1 6 27 120 534 2,256 8,969 33,058 114,149 360,508 930,588 1,350,652

the last 3 are: 782,536 90,280 276

Sorry about that. So the second one has 15 terms including 1, the first has 12 including 1. An icosahedron has 12 vertices and 15 faces, so this might be an icosahedral symmetry. Also note that the symmetry group of permutations on 12 objects (the set of edge pieces) has the Mathieu group M[sub]12[/sub] as a subgroup, which is well-connected to coding theory.
0
skipper

@skipper-wJtaxo • Jan 26, 2010

A Fibonacci series (recurrence) is: a[sub]n[/sub] = a[sub]n-1[/sub] + a[sub]n-2[/sub], with a[sub]1[/sub]= a[sub]2[/sub] = 1.

So a[sub]3[/sub]= 1 + 1, a[sub]4[/sub]= 2 + 1, a[sub]5[/sub]= 3 + 2, ...

With the 3x3x3 cuboid or "quasi-cube", the recurrence is: a[sub]n[/sub]= 6a[sub]n-1[/sub] + 9b[sub]n-2[/sub], b[sub]n[/sub] = 6a[sub]n-1[/sub] + 6b[sub]n-2[/sub], with a[sub]1[/sub]= b[sub]1[/sub] = 9.

This is a recurrence in two variables that add together, or a[sub]n[/sub] + b[sub]n[/sub] = k, where k is the subtotal. Subtotals are just "figures" or tokens, really. Note that in the 3x3x3 recurrence, a and b are not moves in FTM or QTM. As far as arithmetic goes, the last 3 terms in the second (QTM) series are borrowed by the FTM, so are arithmetically subtracted during the enumeration, which is an exhaustive logarithmic series that ends at n = 11 for the first and n = 14 for the second; the difference in the number of terms, and the 'quotient' function as a fraction of the total, are tied up in the above recurrence for the 3x3x3.

The other useful detail is that the 2x2x2 which is represented by an unformulated n (apart from the ordering) is a subtotal of the 3x3x3 because the "corner cubies" are part of the 3x3x3, so must contribute the contents of the table to a total ( ~ 43 quintillion, quite a bit larger than for the 2x2x2 with a mere ~ 3 million).
0
skipper

@skipper-wJtaxo • Jan 30, 2010

Let's look at the first few members of each sequence.

1 9 54 321 1,847
1 6 27 120 534

If I call these sa and sb, then I have sa(0), sa(1), ..., sa(k), sa(n), and sb(0), sb(1), ..., sb(k), sb(n).
sa(0) = sb(0), that's easy. So if I start with k = 1, and divide by 6 to set sb(1) = the identity.

I can assume that, since sb is for the QTM and each of 6 "cubes" is only one quarter turn from the solution. So if I carry this div 6 operation through the rest of the sequences:
if I assume div and mod operations

1,0; 4,3 ; 20,0; 89,0.
For sa:
1,3; 9,0; 53,3; 307,4
[that's better, 6 divides 6 once, and the remainder is 0]

Ok, so the first sequence already has mod 6 = 0 terms; there are primes div 6 and 53 is the first nontrivial one. I need to decompose these into terms like p + 1. Then by subtracting 1 from any subtotal, I get smaller factors by dividing them out by factors of 2 and 3. The modularity at n = 0 is 2x3 = 6 (I can assume this relation is true for all n, and find a contradiction later).

I believe this is exactly what you do when you solve a messed-up Rubik's cube - you factor out large primes, reducing the problem. Since the cube can only do this in 2-dimensions at a time (the slices are planes, the elements move or translate along them), dividing by 3 must be connected to a two-move sequence or to the corner pieces with 3 facets which can be colored - other than black. Perhaps the second option is connected to the "twist operator" that orients a corner cubie in place.

You can twist a single corner and return it to where it started in just two moves (see if you can prove this. The moves must be on adjacent faces and several other cubies get moved, however it is the case that one corner element returns to where it started, and it is twisted. So how many moves are needed to flip at least one edge piece or cubie? These have one more inner facet, in the rotation "actions" applied to all components, so this suggests a flip requires 3 moves.
0
skipper

@skipper-wJtaxo • Jan 30, 2010

Ok, another clue for mathematicians.
If you imagine the numbers are piles or stacks of Rubik's cubes, each looks different, but some of the differences are "identical" in some respect - this should be obvious since there are 8 ways to choose which vertex represents a "center" for any two or three faces, and 1 of 3 rotations of the elements "in" a face - these in the Pocket Cube are 1/2 of the elements, in the original 1/3.

This 2-3 relation is also obvious - the 2-ary number corresponds to the dihedral nature of edges of a cube (sliced or not) and 3 is the number of spatial dimensions. Single moves are binary and reflexive, since m = -(m.m.m) = m' and vice-versa. IOW a single forward m (clockwise convention) eliminates three reverse turns, likewise a single reverse turn eliminates three forward turns.

The T,-T symmetry is equivalent to parity (of even cycles). The 3-ary number is the twist group acting on elements with three facets - the vertex set, or 1/2 of it at T or -T. The layers introduced by a double sliced cube (the 3x3x3) are a separate set of elements - you can arbitrarily reduce the algebra of either by removing some or all of the stickers. The black plastic frame (B) is then an open ball on C the set of colors.

Black means a base of b for the logarithmic function, logb(S) where S is any "symbol", i.e. integer total or subtotal in Tn or Tm. The full table is a map of the intersecting subtotals indexed by the full (outer) moves n, and the single (inner) moves m. The first has 12 places if the zeroth is 1, the second likewise has 15 places.

The Platonic solids with this kind of spatial edge-vertex-facet symmetry are the icosahedron and the dodecahedron. If you permute a set of fixed colors over the elements of a polyhedron such as these dual pairs, you generate a symmetry group of rotations. If you slice such a solid so the elements can exchange places (with some abstract swapping function, which may also rotate and reflect the elements. Ic has 12 vertices and 15 [(oops) edges] and 20 faces (or facets).

So imagine the n actually label a logarithmic version of the vertices of Ic, and m label the [edges]. You need to find the log[sub]n[/sub] and log[sub]m[/sub] functions that reduce each edge to the same length as the identity e = 1.
0
skipper

@skipper-wJtaxo • Feb 2, 2010

Suppose there is a word, or 'work' W, in several parts (here, any sort of construction that be considered "computational" is possible, a building or bridge, a computer program, or a concerto).

Let this word have a cycle C with length n, where in each part or place of n, a second inner cycle (the machine, M, acting) c(m) descends and ascends within the nth part, so that all harmonics of the work, or all possible words, or all stresses, strains, and tensions are explored, all nodes of the structure that can be said to occupy a causal place in the structure are visited , i.e. the set of all "motions of small bodies, variously figured", then M has a cycle length greater than |C(n)|.

In the Pocket Cube this is a factor of 3, since n is 12 parts (FTM), and m is 15 parts (QTM). What the tables and totals represent is something like how many notes or chords are in the "work", or how many elements in the structure can be "figured and moved". Of course these are all visited by a black plastic base, what "expands" is the number of monotone products, or, you can view each permutation as some notes, in an abstract key, the key of "red, white, and green", say. Black represents the "rests", etc.
😎:smile:;-)
0
skipper

@skipper-wJtaxo • Feb 2, 2010

One other detail I think is important: the figure I keep mentioning which you can form with an algorithm: "X,Y',Z',X", as long as XYZ are three faces that have a common vertex.

This construction forms what logicians and mathematicians call a manifold (a program is a manifold, or the data structures are, the algorithms compute relations between such structures, which can be as layered or structured as required). This has the initial word "XX" which is a square move, or one which eliminates the "twist" if a face is only 1/4 rotated (it removes the information about which way the face was turned).

Then a g acts on XX, g: (XX) -> (X,X), another h acts on g(X,X), h: g(X,X) -> g_h(XY',Z'X).

So the word itself with the form described is a split square move (a manifold); h is an internal operator in the cross/anticross group. The cross group is the one with words in it like X'Y or ZX', where the rotations are in opposite senses. The anticross group has words that rotate in the same sense. Here "sense" means essentially the sense of computing "forwards or backwards".

This 4-element word and its equivalents visit a subset of the nodes in the totals listed, if not all of the nodes in the ab(n) sequence. Each time you build this figure, there are always three ways to rebuild it, or choose which face is X, in the next iteration. These words are 63 iterations in length (you return to where you started as with any word that corresponds to an instruction cycle, all have a finite length).

Note the difference between 63 and 89, which is 26, which is the actual number of physical elements, including the centers (which are redundant) in the 3x3x3 cube, which has the edges group (Mathieu's M[sub]11[/sub] and M[sub]12[/sub] sporadic groups). The central 27th element is in the same place as the group of edges in the 2x2x2 structure.
0