I have discovered/stumbled upon a four-digit number s with the following characteristics.
(i) Let p = 3s+1, q = 4s+1. (ii) The Collatz sequence starting at q has p as the next odd number in the sequence; (iii) the next odd number in the sequence after p is a three-digit number r; (iv) The next odd number after r is the terminal value 1. Thus, the sequence started at p contains only three odd numbers and a number of even numbers, all of which are powers of 2.This property is similar to the nature of the sequence started at 3, which passes through 5 before reaching 1. Spoiler-alert: s = 1212, p=3637, q =4849,r=341.
I invite interested readers to use one of the online Collatz sequence generators that are available, starting with the value q given here, and observe the numbers generated.
Thanks for reading! I am interested in @art-rasa’s reactions!
Really interesting discovery! Especially when the result is viewed with logarithmic y-axis.
Thank you for sharing it with us.
Here is another starting value that produces a surprisingly short sequence: 742741. The sequence passes through the odd numbers 17, 13 and 5 before reaching 1. That is, the sequence contains only five odd numbers, despite starting with a six digit odd number.
The starting number 2970965 illustrates the rapid “hailstoning” that is characteristic of Collatz sequences. Since 3*2970965+1 =17*2^18, the next odd number in the sequence is just 17! Thus, one 3x+1 operation followed by 18 halvings took us from a number larger than a million to 17. If we continue the calculations, the odd numbers 13,5 and 1 follow.
Other starting values to try are 2901, 10005 and 17749. Also 70997. And 25861 leads to 4849. In the sequence 18197, 853, 5,1, note that each odd number visited is less than its predecessors.
With a(n), n>0, of A000002 - OEIS, if we use 10 a(n)+3 as the starting point, the resulting Collatz sequence contains only three odd numbers: (i)10 a(n)+3, (ii) 5, and (iii) 1, plus a number of intervening even numbers that are of little interest and need not be recorded or discussed. Similarly, if we start at 100 a(n)+33, the next odd number encountered will be 25. Try, for example, 2133, 8533, 34133 and 136533.For these four cases, the odd numbers seen after the start will be 19,29,11,17,13,5,1.
[quote=“art-rasa, post:2, topic:9771”]
Thank you for sharing it with us
[/quote] It is my good fortune to have access to this forum, where members are knowledgeable, courteous, helpful and tolerant. I appreciate the patience shown by the moderators, given that they could have viewed my post as “off-topic”.
The Fortran bit-intrinsic function trailz was of great help to me in running and studying many Collatz sequences rapidly.
The intrinsics trailz() and leadz() were both added to the language in f2008. I have found several uses in my own applications for both of them since that time.
edit: This might be a little offtopic, but the gfortran documentation of leadz() is incorrect at LEADZ - The GNU Fortran Compiler The correct output for the example is 31 not 8.
Sounds like they may not be short enough(?) but if they are, we are always looking for interesting examples to put in the intrinsic descriptions for fpm-man/fman …
https://urbanjost.github.io/M_intrinsics/index3.html
the examples or trailz() and leadz() lack an example showing a purpose for the routines, which I think makes the examples far more interesting.
A nice complement to the trailz function would be a subroutine trimz(v,nz,kz), which would take the integer v as an input argument, and return nz, the number of trailing zeros in v, and the “kernel” kz that results from removing the trailing zeros. For example, call trimz(3*1365+1,nz,kz) would return nz=14,kz=1 and call trimz(3*37+1,nz,kz) would return nz=4,kz=7). What do you think about this?
program trimzX
integer :: v,x,y,nz
x=25; v=3*x+1
call trimz(v, nz, y)
print '(3i6)',v,y,nz
contains
subroutine trimz(v,kz,nz)
integer, intent(in):: v
integer, intent(out) :: kz,nz
nz=trailz(v)
kz=v
if(nz > 0) kz=rshift(v,nz)
return
end subroutine trimz
end program trimzX
type or paste code here
A TRAILZ() with the output used on a SHIFTR() would do that, I think.
program demo_trailz
implicit none
call printit(3*1365+1)
call printit(3*37+1)
contains
subroutine printit(ii)
integer,intent(in) :: ii
integer :: nz, kz
character(len=*),parameter :: show32 = '(1x,"value=",i4,", value(bits)=",b32.32,1x,", trailz=",i3)'
print '(a)', repeat('-',80)
print show32, ii, ii, trailz(ii)
call trimz(ii,nz,kz)
print show32, kz, kz, trailz(kz)
end subroutine printit
subroutine trimz(v,nz,kz)
integer,intent(in) :: v
integer,intent(out) :: nz
integer,intent(out) :: kz
nz=trailz(v)
kz=shiftr(v,nz)
end subroutine trimz
end program demo_trailz
--------------------------------------------------------------------------------
value=4096, value(bits)=00000000000000000001000000000000 , trailz= 12
value= 1, value(bits)=00000000000000000000000000000001 , trailz= 0
--------------------------------------------------------------------------------
value= 112, value(bits)=00000000000000000000000001110000 , trailz= 4
value= 7, value(bits)=00000000000000000000000000000111 , trailz= 0
Yes, this is correct. However, if a processor evaluates trailz() in a loop where the bits are examined one by one, then the kz value would be evaluated naturally during that process with no additional effort (i.e. no separate shift operation afterwards). I wonder if this is a common enough operation to warrant a new intrinsic?
One has to check that a subsequent step in which nz will be used is valid even when nz is zero. At other times, nz may be used for bookkeeping purposes.Here is a short code with this idea, to calculate and output the Collatz sequence for a given starting value:
program xncoll
integer :: x,v,y,nz,ns,x0
integer,parameter:: ITRLIM=55
read *,x ; x0=x; ns=0
print *,'it x y nz ns'
do i=1,ITRLIM
call ncoll(x,y,nz)!y=ncoll(x)
ns=ns+nz
print '(i3,2x,2i6,2i4)',i,x,y,nz,ns
x=y
if(x.ne.1)cycle
print *,' 1 Reached',i,' ITERS'
exit
end do
if(i.eq.ITRLIM+1)stop 'ITERS terminated'
print *,'x0=',x0
contains
subroutine ncoll(x,y,nz)
integer,intent(IN)::x
integer,intent(out)::y,nz
integer :: v
v=x; if(mod(x,2).ne.0)v=3*v+1
nz=trailz(v)
!print *,x,v,nz
y=n;if(nz>0)y=shiftr(v,nz)
return
end subroutine
end program xncoll
! Run this program with a starting value of 789 for fun!
Here is a stunningly short Collatz sequence. The starting number is x_0=8738133.After starting, the odd numbers passed through are 25,19,29,11,17,13,5 and then 1 is reached. Note that all these are less than x0 – indeed, they are tiny numbers, all expressible with one or two decimal digits.
Note that
3x_0+1=26214400=(5^2)(2^20)
Another starting value to try: 742741. The sequence passes through 17, 13 and 5 and then to 1.
So if there are a series of values N and corresponding values 2N which
will always converge to one, and for which there are no other values below
them that will have more steps, and the 2N values only have one more step
than the N values then if that is an infinite series (incidentally(?) with
the values becoming more sparse), then since there is always another 2N
that is solvable and has the maximum number of steps does that prove
all values have a solution? Just playing, but would that even prove the
conjecture? It has been a long time since I played with anything similar.
For example, all the values in column 1 should have the most steps of any
value up to that value, and have a matching value twice the size that is
not only also a value with the same attributes, but with only one more step
but with no other values between with more steps.:
3 6
9 18
27 54
15733191 31466382
63728127 127456254
268549803 537099606
670617279 1341234558
4890328815 9780657630
31694683323 63389366646
202485402111 404970804222
There are so many threads in this series that are apparently not leading
to proofs I see how it had attracted interest.
I did not see these values in
so hopefully not a commonly identified sequence.
Thanks for your thoughtful post. If I understand your approach correctly, you wish to apply the principle of induction to patterns of correspondence between Collatz sequences started from closely related starting points. There are many posts of this type in math.stack-overflow, but it is a bit difficult to read many of them without being aware of the conventions being followed.
May I suggest that we trim the reporting of Collatz sequences by disclosing only the newly computed odd numbers, as follows?
- Start with a prescribed initial value x_0 for x. Repeat the following steps:
- set v = x. if x is odd, set v = 3x+1
- in the binary representation of v, count the number of trailing zeros
- Remove the trailing zeros, and set x = the number that remains. Record this number in the program output.
- If x =1, stop the calculation. Otherwise, go back to step 2.
For example, starting with x_0= 117, the reported output would be: 11, 17, 13, 5, 1. For this case, note that all the output values are less than the starting value. Another similar example has a starting value of 7281. You may also try 2501, 2901 and 605. I wonder if we can decipher how rapid reduction in number size occurs because of bursts of dividing by 2 (or, equivalently, removing many trailing zeros). Is there a pattern in a number just prior to such a burst? Could such a pattern be used in trying to anticipate that the sequence is nearing 1 ?
After gaining some experience with different starting values and observing the resulting patterns, it is possible to construct interesting sequences by applying rules rather than by running a computer program. For instance, we can prove that 136533 starts a sequence that merges with the sequence that starts with 25. In fact, the next odd value for x_0= 136533 is 25!
The starting values 201 and 12885 are of high interest because they are multiples of 3 and, therefore, cannot be reached via a Collatz sequence started at another point. They both generate a sequence in which the odd values recorded are 151,227,341,1 .
The Collatz sequences starting from 3 and 3637 are strangely similar in that, apart from some intermediate even numbers that we may ignore, they contain only three odd numbers: the starting value, one intermediate value, and the terminal 1. Consider 3:5:1 and 3637:341:1 . (You can verify using an online calculator.
The numbers in the left column of your table are to be found in OEIS. The description is:
“Inputs n that yield a record-breaking value of A008908(n)/(log_2(n)+1) for the Collatz conjecture.”
The trailz function is also useful in deciding whether a four digit year is a leap year.
integer:: yyyy, ntz
logical :: cent, leap
ntz = trailz(yyyy)
cent = mod(yyyy,100).eq.0
if(cent)then
leap = ntz > 3 !yrs divisible by 400
else
leap = ntz > 1 ! yrs divisible by 4
endif
This calculation can be used in a day_of_week(yyyy,mm,dd) routine. One would need to insert code to cover the tricky issue that The year before AD 1 is 1 BC, and there was no year 0000, so the question of whether year 0000 was a leap year is moot.
I read a news article about an unfortunate person whose date of birth had been recorded as Feb 29 of a common (not-leap) year.
For your enjoyment/further confusion, the saying of an AI engine on this topic:
" Yes, according to the Julian calendar, the year 1 BC was a leap year. This is because the Julian calendar, introduced by Julius Caesar, stipulated that a leap year should occur every four years, and 1 BC would be the fourth year after the initial introduction of the calendar in 45 BC. However, due to a misunderstanding by Roman priests, the leap day was not consistently applied in the early years, creating some discrepancy in whether 1 BC was actually a leap year in practice.
After Caesar’s death, the Roman priests in charge of the calendar mistakenly added a leap day every three years instead of four.
This error was eventually corrected by Caesar’s successor, Augustus, who adjusted the calendar to skip leap days for a few years to align it with the solar cycle again.
- [
Although the Julian calendar rules would have made 1 BC a leap year, the “leap year error” makes it uncertain whether it was actually observed as such.
In both the proleptic Julian and [Gregorian calendars] 1 BC is considered a leap year.
- As year 0 AD didn’t exist, does that mean 1 BC was a leap year?
Oct 2, 2020 — Unfortunately, he was murdered in 44 BC, and the Roman priests, tasked with managing the calendar, misunderstood the ru…
This is because the Julian calendar, introduced by Julius Caesar, stipulated that a leap year should occur every four years, and 1 BC would be the fourth year after the initial introduction of the calendar in 45 BC. However, due to a misunderstanding by Roman priests, the leap day was not consistently applied in the early years, creating some discrepancy in whether 1 BC was actually a leap year in practice.
In 45 BC, Julius Caesar introduced a new calendar that included leap years (an extra day every four years) to better align the calendar with the Earth’s orbit around the sun.
After Caesar’s death, the Roman priests in charge of the calendar mistakenly added a leap day every three years instead of four.
45 BC, 42 BC, 39 BC, 36 BC, 33 BC, 30 BC, 27 BC, 24 BC, 21 BC, 18 BC, 15 BC, 12 BC, 9 BC, 8 AD, 12 AD were regarded as leap years before the advent of the Gregorian calendar. See AstroPages | Leap Year | Western Washington University for details.