amazing long cycle of Collatz-type function based on Lucas representation

[Geoffrey Caveney]

Sequence A130310 describes the unique "minimal (or "greedy") Lucas representation of n, in which L(0) = 2 and L(2) = 3 are not allowed in the same representation (hence the correct representation of the integer 5 is 1010 rather than 101). A binary system of integers with Lucas numbers (A000032) as a base."

This is analogous to the Zeckendorf representation of integers as sums of non-consecutive Fibonacci numbers, but with Lucas numbers, the additional restriction prohibiting the co-occurrence of 2 and 3 is necessary to make the Lucas representation unique, as shown by Brown in 1969. Relevant information and sources are available at A342089, the sequence of numbers that have two such Lucas representations without the restriction on 2 and 3.

Define a number as "Lucas-even" if the last digit of its Lucas representation is 0 AND the removal of the last digit 0 produces a valid minimal Lucas representation of a smaller integer. The second condition is necessary because removing the final 0 from representations ending in ...1010 is NOT valid -- the resulting ...101 would be equivalent to the co-occurrence of 3 and 2 and thus it is not allowed.

Define a number as "Lucas-odd" either if the last digit of its Lucas representation is 1 OR if the last four digits of its Lucas representation are 1010.

Now define a Collatz-type function based on this Lucas representation:

If n is Lucas-even, remove the last digit 0 of its Lucas representation to obtain f(n) ;

If n is Lucas-odd, f(n) = 2n.

Note that removing the last digit 0 is approximately equivalent to division by phi = 1.618....

As in the classical Collatz function, the orbit of an integer is the sequence produced by the repeated iteration of the function.

Two simple cycles of this function are 2, 4, 3, 1, 2, ... and 5, 10, 5, .... Many small integers have orbits reaching one of these two cycles, such as 36, 22, 14, 8, 6, 12, 9, 18, 11, 7, 4, 3, 1, 2, ...;  28, 16, 32, 19, 13, 26, 17, 34, 68, 41, 27, 54, 33, 21, 12, 9, 18, 11, 7, 4, 3, 1, 2, ...;  and 30, 20, 40, 25, 15, 10, 5, ....

But there is also an amazingly long cycle beginning with 23, which is the reason for this post:

23, 46, 92, 184, 113, 71, 142, 89, 178, 111, 222, 444, 888, 1776, 1097, 679, 1358, 2716, 5432, 10864, 6713, 13426, 8297, 5129, 10258, 6341, 12682, 7839, 15678, 9691, 19382, 11979, 7403, 4576, 2827, 5654, 3493, 6986, 4317, 2669, 5338, 10676, 6597, 13194, 8153, 16306, 10077, 6229, 12458, 7701, 15402, 9519, 5883, 3636, 2247, 1389, 858, 531, 327, 654, 403, 806, 497, 994, 613, 1226, 757, 469, 938, 581, 1162, 719, 443, 886, 547, 339, 678, 1356, 837, 519, 1038, 641, 397, 244, 488, 301, 187, 374, 748, 461, 922, 569, 353, 706, 437, 269, 538, 1076, 2152, 1329, 823, 1646, 1017, 629, 388, 241, 482, 299, 598, 371, 742, 459, 283, 176, 352, 219, 438, 271, 167, 104, 63, 126, 77, 49, 98, 61, 37, 24, 48, 31, 62, 39, 23, ...

This cycle comprises 132 integers, including 16 integers < 100, 65 integers between 100 and 1,000, 38 integers between 1,000 and 10,000, and 13 integers > 10,000. The largest integer in this cycle is 19,382, the 30th iterate of 23. 

An interesting value in the cycle is 15,402 = 15,127 + 199 + 76, which gives the Lucas representation 100000000101000000000. This is the first of 8 consecutive Lucas-even numbers in the sequence, resulting in the much smaller Lucas-odd number 327 = 322 + 4 + 1, or 1000000001010 in Lucas representation.

For the record, believe it or not, I did NOT use any AI program to discover or compute this cycle. I was simply exploring the function out of curiosity and testing the orbits of small integers when I stumbled across the orbit of 23. It was actually not too difficult to compute each term by utilizing the b-file of A130310 for integers up to 10,000.

Geoffrey Caveney

[Geoffrey Caveney]

Incredibly, this Lucas-Collatz function has another very long cycle beginning with 70. This cycle contains 122 integers and reaches several values greater than 1 million, the largest of which is 1,863,240.

70, 140, 280, 560, 345, 690, 1380, 2760, 1705, 1055, 2110, 1305, 2610, 5220, 3225, 6450, 3985, 7970, 4925, 3045, 6090, 3765, 7530, 4655, 9310, 5755, 11510, 7115, 14230, 8795, 5435, 3360, 6720, 13440, 8305, 16610, 10265, 6345, 12690, 25380, 15685, 9695, 19390, 11985, 23970, 14815, 9155, 18310, 11315, 22630, 13985, 27970, 55940, 111880, 69145, 42735, 85470, 52825, 105650, 65295, 40355, 24940, 15415, 30830, 19055, 38110, 76220, 152440, 304880, 188425, 376850, 232905, 465810, 931620, 1863240, 1151545, 711695, 1423390, 879705, 1759410, 1087375, 672035, 415340, 256695, 158645, 317290, 196095, 121195, 242390, 149805, 92585, 57220, 35365, 70730, 43715, 87430, 54035, 33395, 20640, 12755, 25510, 15765, 9745, 19490, 12045, 7445, 4600, 9200, 5685, 3515, 7030, 4345, 2685, 1660, 1025, 635, 1270, 785, 485, 300, 185, 115, 70, …

It is interesting that the Lucas representation of 70 = 47+18+4+1, which is similar to that of 23 = 18+4+1.

[Allan Wechsler]

Geoffrey,

These examples are indeed quite eye-popping.

I take it that nothing comparably interesting happens when you use the standard Zeckendorf expansion?

-- Allan

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFhKorUTBFvePFh7ws_5Z8JJW2Zsn5SH%2B-JnJKcRsR3V5ZALfQ%40mail.gmail.com.

[Geoffrey Caveney]

Allan, I'm glad that you also find these long hailstone sequence cycles interesting.

In fact, myself and Haoxuan (Jason) Dong are also investigating the analogous function with the standard Fibonacci-Zeckendorf representation. There are quite interesting phenomena there as well, but nothing as immediately stunning as these long cycles of 23 and 70 in the Lucas-Collatz function. It appears by contrast that in the Fibonacci-Zeckendorf variant, the orbits of all integers reach the simple cycle 1, 2, 1, .... Of course we do not have a proof of this conjecture.

Geoffrey

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGHscO8%3DRZq%2B_8DP-sN9WuFL5wyc2vyFgCBZyzkOsD-g8w%40mail.gmail.com.

[Allan Wechsler]

One thing that would really help to think about this is a procedure for doubling a number in Zeckendorf notation -- I suspect that the corresponding procedure for doubling a number in the corresponding Lucas notation would be identical except for some startup transients.

The obvious procedure is to decode the Zeckendorf representation, double the number in a more amenable representation, and then re-encode it. But I think that we might be able to improve this to a state machine, where the machine receives a Zeckendorf representation one bit at a time starting from the least significant end, and outputs results one bit at a time (delayed by three or four bits). My initial fiddling suggests this could be done with on the order of half a dozen states. If that's correct, then probably a "Lucas representation" doubler could be achieved just by picking a different start state (possibly a new, bespoke state, but I suspect at most one).

-- Allan

If nobody supplies the correct procedure, I might try to work it out this evening.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFhKorUPgLGWAkS%2BtJS10s-XatuHn%2B8boePoZB%2BhYj0qfwjyOw%40mail.gmail.com.

[Geoffrey Caveney]

Allan,

It appears that the paper "Complexity of Linear Subsequences of Fibonacci-Automatic Sequences", published on arXiv by Moradi, Rampersad, and Shallit in March of this year, addresses this question:

https://arxiv.org/abs/2603.21645

The abstract states:"We construct automata with input(s) in Fibonacci representation (also known as Zeckendorf representation) recognizing some basic arithmetic relations and study their number of states. We also consider some basic operations on Fibonacci-automatic sequences and discuss their state complexity. Furthermore, as a consequence of our results, we improve a bound in a recent paper of Bosma and Don. We also discuss the state complexity and runtime complexity of using a reasonable interpretation of Büchi arithmetic to actually construct some of the studied automata recognizing relations."

Section 3 "Recognizing Relations" and 3.2 "Multiplication" on pp. 8-12 address your question. The authors even draw a nice diagram on p. 9 with the caption "Figure 2: Multiplication by 2 in Fibonacci representation."

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGFyfxL95hQsc64vzv%2BKySFUKzgskdB-Jn92mBzj2gWwKQ%40mail.gmail.com.

[Jeffrey Shallit]

You can very easily get the automata for arithmetic on Lucas representations with Walnut.  The idea is to have a Zeckendorf-to-Lucas automaton A, so that one can start with a Lucas representation, do the conversion backwards with A, do the arithmetic in Zeckendorf (built in to Walnut), then convert back with A.  This gives the minimal automaton.  

On Tue, Aug 25, 2026 at 1:27 PM Allan Wechsler <acw...@gmail.com> wrote:

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGFyfxL95hQsc64vzv%2BKySFUKzgskdB-Jn92mBzj2gWwKQ%40mail.gmail.com.

[Geoffrey Caveney]

I observe that the numbers I define as "Lucas-odd" are almost an exact match with the sequence A094350, which is based on sequence A094291. (A094350 is defined as "Numbers n such that A094291(n) is not a square.") However, there is one term of A094350 which is not Lucas-odd by my definition: 41. It is not easy to double-check this value, because A094291 only lists values up to a(30). Could someone who is familiar with the subject matter of these sequences double-check the accuracy of the term 41 in A094350?

Thanks,

Geoffrey

[Hugo Pfoertner]

The first terms of https://oeis.org/A094350, together with the terms of https://oeis.org/A094291 are:

[2, 2], [5, 18], [6, 40], [9, 525], [13, 17640], [16, 261360], [17, 637065], [20, 10020010], [23, 155739584], [24, 393853824], [27, 6347376360], [31, 261312846300], [34, 4273916775040], [35, 10851741811625], [38, 181162302621300], [41, 2992431188360250], [42, 7709033255332500], [45, 129416878280289600], ...

so 41 is confirmed as a term in A094350.

[Geoffrey Caveney]

Thank you Hugo!

Geoffrey 

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.

To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/12ecec6a-1b6f-44c5-ae5c-bcfe7a0748bcn%40googlegroups.com.

[Geoffrey Caveney]

Many further thanks to Hugo for computing the terms of A094350 up to 158. The only two terms in A094350 that are not "Lucas-odd" numbers are 41 and 117, which is the Lucas number 76 + 41. Something interesting is going on here, but I don't understand what it is. The minimal Lucas representation of 41 is 10100010. Lucas-odd numbers have representations ending in 1 or in 1010.

Geoffrey

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.

To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

[Hugo Pfoertner]

I'm currently calculating a b-file for A094291. It will have approximately 2000 terms before the term length limit of 1000 digits is exceeded. This will also allow for more terms of A094350. It will take a little while, though.