Implementation of PRNG based on the Collatz conjecture

73 views
Skip to first unread message

osobli...@gmail.com

unread,
Nov 17, 2021, 5:09:01 AM11/17/21
to
In paper "Pseudo-random number generators based on the Collatz conjecture":

https://sci-hub.se/10.1007/s41870-019-00307-9

authors presented several PRNGs. First seems to be the best. They claim they proved that its period is at least 2^32. This prove is wrong in my opinion and we can find the seeds for which generator will fall into short trivial cycle.

Problem is that:
a) definition of algorithm is a bit unclear,
b) maybe I made a mistake in my code or don't understand it wrong.

Would anyone be kind to write their own code and check the generator? If you do not understand something in the publication, I can help. Here is my code in Python:

https://pastebin.com/6BpzFj69

If someone checks the code or creates their own code I will give you broken seeds. For now, I don't want to suggest any result.

PS Don't try to use math.log(x,2) it doesn't work properly on big numbers.


Richard Heathfield

unread,
Nov 17, 2021, 5:42:23 AM11/17/21
to
On 17/11/2021 10:08, osobli...@gmail.com wrote:
> In paper "Pseudo-random number generators based on the Collatz conjecture":
>
> https://sci-hub.se/10.1007/s41870-019-00307-9

My ISP has blocked that site because of a court order.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

osobli...@gmail.com

unread,
Nov 17, 2021, 5:55:17 AM11/17/21
to
Maybe try just https://sci-hub.se and find there "Pseudo-random number generators based on the Collatz conjecture".

Richard Heathfield

unread,
Nov 17, 2021, 6:07:45 AM11/17/21
to
Censorship is at work here:

Secure Connection Failed

An error occurred during a connection to sci-hub.se. PR_CONNECT_RESET_ERROR

The page you are trying to view cannot be shown because the
authenticity of the received data could not be verified.
Please contact the web site owners to inform them of this problem.

Learn more…

So I clicked on "Learn more" and...

Secure connection failed and Firefox did not connect

This article explains why you may see a Secure Connection Failed or a
Did Not Connect: Potential Security Issue error page and what you can do.

If you see a Warning: Potential Security Risk Ahead error page, see
the What do the security warning codes mean? article.
To troubleshoot other error messages, see Websites don't load -
troubleshoot and fix error messages.

Table of Contents

Secure connection cannot be established
Secure Connection Failed
Did Not Connect: Potential Security Issue
Website issues
TLS version unsupported
HSTS required
Security software conflict
Incorrect system clock
Other secure connection issues

So I thought "okay, maybe this is https" so I dropped the "s" and went
for: https://sci-hub.se/

Next, I got this:

Sorry, this page is not available through Virgin Media

Virgin Media has received an order from the High Court requiring us to
prevent access to this site. For more information about the order and
your rights, please click the relevant link below.
I’m a Virgin Media home broadband customer
I’m a Virgin Media Business customer

Find out more general information:
I’m a Virgin Media home broadband customer
I’m a Virgin Media Business customer


Next, I was given a list of sealed court orders:

https://www.virginmedia.com/help/list-of-court-orders

which includes:

05/02/2021


(1) Elsevier LTD

(2) Springer Nature LTD


sci-hub.se


So the UK courts have decided that either or both of those limited
companies has the right to suppress freedom of expression.

osobli...@gmail.com

unread,
Nov 17, 2021, 6:20:39 AM11/17/21
to
You could be able to download it from here:

https://altosharepdf.com/share/5ff2ee173ed04e4ab6a1879b6aa444a8

Richard Heathfield

unread,
Nov 17, 2021, 6:29:11 AM11/17/21
to
On 17/11/2021 11:20, osobli...@gmail.com wrote:
> You could be able to download it from here:
>
> https://altosharepdf.com/share/5ff2ee173ed04e4ab6a1879b6aa444a8

Indeed I could. Thank you.

https://en.wikipedia.org/wiki/Streisand_effect

"When the French intelligence agency DCRI tried to delete Wikipedia's
article about the military radio station of Pierre-sur-Haute, the
article became French Wikipedia's most viewed page." - Wikipedia

"The Net interprets censorship as damage and routes around it" - John
Gilmore.

And now I have a PDF to read.

wizzofozz

unread,
Nov 17, 2021, 5:07:38 PM11/17/21
to
Op 17-11-2021 om 11:08 schreef osobli...@gmail.com:
I don't have much time now, but here is my take on it (code at the end).
When I was implementing it, it occured to me that I am not sure about
the lsb and msb of Ek (I get the same vector for 26, but later I need to
convert it to a number). Also, when they talk about 'the first k
elements of vector x' I'm not sure.
I use many intermediate steps in alg1. That's because of 'debugging' and
no time to fix it.
I use a generator which you can ask for the next element with next().
Note: I don't understand what I'm doing. Just trying to follow the paper
and implement it. Perhaps you can compare it to your code.

Ozz


#!/bin/python

def T(n):
return (n*3**(n%2)+n%2)/2

def Tk(n,k):
if k==1:
return T(n)
else:
return Tk(T(n),k-1)


def Xk(n,k):
return Tk(n,k)%2


def log2(n): # rounds up
i=0
while 2**i < n:
i += 1
return i

def Ek(n):
e=[0]
e.extend([Xk(n,k) for k in range(1,log2(n)+1)])
return e

def Eknum(n): # don't know if lsb/msb is correct
e=Ek(n)
return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))])

def b(n):
return n>>(log2(n)-95)


def alg1(n):
ao=0
while True:
atmp=bin(b(n+ao)^Eknum(n+ao))[2:97]
# print atmp
s=0
for i in range(len(atmp)):
p = 2**(len(atmp)-i-1)
# print p
s = s + int(atmp[i])*p
# print s
#atmpn=sum([atmp[i]*2**(len(atmp)-i-1) for i in range(len(atmp))])
a=(s+ao)%2**128
# print a
ao=a
yield a


x=2**95+100
c=alg1(x)
print [c.next() for i in range(20)]




osobli...@gmail.com

unread,
Nov 17, 2021, 6:14:13 PM11/17/21
to
Something is wrong with c.next(). I'm getting:

<generator object <genexpr> at 0x000001E8189B54A0>

osobli...@gmail.com

unread,
Nov 17, 2021, 8:05:29 PM11/17/21
to
This:

def T(n):
return (n*3**(n%2)+n%2)/2

def Tk(n,k):
if k==1:
return T(n)
else:
return Tk(T(n),k-1)

def Xk(n,k):
return Tk(n,k)%2

def log2(n): # rounds up
i=0
while 2**i < n:
i += 1
return i

def Ek(n):
e=[0]
e.extend([Xk(n,k) for k in range(1,log2(n)+1)])
return e

def Eknum(n): # don't know if lsb/msb is correct
e=Ek(n)
return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))])

def b(n):
return n>>(log2(n)-95)

Looks fine. It is the same as I did, with one exception. Here:

e.extend([Xk(n,k) for k in range(1,log2(n)+1)])

I think yoy shouldn't add 1. Let's try encoding vector for 26. It will be:

0b10010

But it could be 1001. The same example is in the publication:

"Example 2 The encoding vector of 26 is the vector {0, 1, 0, 0, 1}."

I don't understand alg1, so I can't tell whether all code is okay or not.

osobli...@gmail.com

unread,
Nov 17, 2021, 8:53:17 PM11/17/21
to
Unfortunately, it looks like there is another problem. If we consider:

> def T(n):
> return (n*3**(n%2)+n%2)/2
>
> def Tk(n,k):
> if k==1:
> return T(n)
> else:
> return Tk(T(n),k-1)
>
> def Xk(n,k):
> return Tk(n,k)%2
>
> def log2(n): # rounds up
> i=0
> while 2**i < n:
> i += 1
> return i
>
> def Ek(n):
> e=[0]
> e.extend([Xk(n,k) for k in range(1,log2(n))])
> return e
>
> def Eknum(n): # don't know if lsb/msb is correct
> e=Ek(n)
> return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))])

for n=9 we will get:

0b11

but it could be:

9,14,7,11 --> 0b1011

The code does not take into account the first number - 9 mod 2 in this case. We can fix this easy by:

def Ek(n):
e=[n%2]
e.extend([Xk(n,k) for k in range(1,log2(n))])
return e

Jens Stuckelberger

unread,
Nov 17, 2021, 9:33:48 PM11/17/21
to
On Wed, 17 Nov 2021 23:07:34 +0100, wizzofozz wrote:

> Op 17-11-2021 om 11:08 schreef osobli...@gmail.com:
>> In paper "Pseudo-random number generators based on the Collatz
>> conjecture":
>>
>> https://sci-hub.se/10.1007/s41870-019-00307-9
>>
>> authors presented several PRNGs. First seems to be the best. They claim
>> they proved that its period is at least 2^32. This prove is wrong in my
>> opinion and we can find the seeds for which generator will fall into
>> short trivial cycle.
>>
>> Problem is that:
>> a) definition of algorithm is a bit unclear,
>> b) maybe I made a mistake in my code or don't understand it wrong.
>>
>> Would anyone be kind to write their own code and check the generator?
>> If you do not understand something in the publication, I can help. Here
>> is my code in Python:
>>
>> https://pastebin.com/6BpzFj69
>>
>> If someone checks the code or creates their own code I will give you
>> broken seeds. For now, I don't want to suggest any result.
>>
>> PS Don't try to use math.log(x,2) it doesn't work properly on big
>> numbers.
>>
>>
>>
> I don't have much time now, but here is my take on it (code at the end).

The implicit message being, of course, "if I can do this as an
afterthought in my limited spare time just imagine what I could do if I
really devoted myself to it."

osobli...@gmail.com

unread,
Nov 17, 2021, 10:18:00 PM11/17/21
to
> When I was implementing it, it occured to me that I am not sure about
> the lsb and msb of Ek (I get the same vector for 26, but later I need to
> convert it to a number). Also, when they talk about 'the first k
> elements of vector x' I'm not sure.

I had the same doubts, but in the end you did the same as I did, except the little miscellaneous I wrote about earlier.

osobli...@gmail.com

unread,
Nov 17, 2021, 11:04:32 PM11/17/21
to
Here still something is wrong. It works well for small numbers, but for n bigger than 2**95 it gives wrong results. For example for 2**95+1 and for 2**95+123 results are the same.

osobli...@gmail.com

unread,
Nov 17, 2021, 11:07:30 PM11/17/21
to
czwartek, 18 listopada 2021 o 05:04:32 UTC+1 osobli...@gmail.com napisał(a):
This is beacuse "return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))])" returns float and it cannot handle big numbers.

wizzofozz

unread,
Nov 18, 2021, 1:41:43 AM11/18/21
to
Op 18-11-2021 om 05:07 schreef osobli...@gmail.com:
> czwartek, 18 listopada 2021 o 05:04:32 UTC+1 osobli...@gmail.com napisał(a):
>> czwartek, 18 listopada 2021 o 02:53:17 UTC+1 osobli...@gmail.com napisał(a):

>>>> Looks fine. It is the same as I did, with one exception. Here:
>>>> e.extend([Xk(n,k) for k in range(1,log2(n)+1)])
>>>> I think yoy shouldn't add 1. Let's try encoding vector for 26. It will be:

Yes, you're right. I changed the log2 function later to round up, and
did not change that one accordingly (not sure if removing +1 moves the
offbyone somewhere else, though ).

>>>>
>>>> I don't understand alg1, so I can't tell whether all code is okay or not.

Ah, I thought that you meant "alg1" by "authors presented several PRNGs.
First seems to be the best." (from your initial post).

>> Here still something is wrong. It works well for small numbers, but for n bigger than 2**95 it gives wrong results. For example for 2**95+1 and for 2**95+123 results are the same.
>
> This is beacuse "return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))])" returns float and it cannot handle big numbers.
>

Therefore the intermediate steps; to 'solve' the overflow.

Regarding your remark about the generator next(); at my end it just
seems to work. I'm using python2.7.

Ozz

wizzofozz

unread,
Nov 18, 2021, 1:44:54 AM11/18/21
to
Op 18-11-2021 om 03:33 schreef Jens Stuckelberger:
The implicit message was a preemptive excuse for the list of comments by
Nick following it :-)

Ozz

osobli...@gmail.com

unread,
Nov 18, 2021, 3:23:27 AM11/18/21
to
I'm using python 3.9, hence I had a problem with c.next(). Now it works, but the problem with return sum([e[i]*2**(len(e)-i-1) for i in range(len(e))]) has to be solved. Now for 2**95+1 and for 2**95+123 results are the same. Where are that "intermediate steps" to 'solve' the overflow? Do you get different results for x=2**95+1 and for x=2**95+123?

osobli...@gmail.com

unread,
Nov 18, 2021, 3:29:50 AM11/18/21
to
I can't xor it:

atmp = bin(b(n+ao)^Eknum(n+ao))[2:97]

TypeError: unsupported operand type(s) for ^: 'int' and 'float'

You probably can in Python 2.7. I'll try to fix this.

osobli...@gmail.com

unread,
Nov 18, 2021, 3:48:34 AM11/18/21
to
Ok, now it works:

def T(n):
return (n*3**(n%2)+n%2)/2

def Tk(n,k):
if k==1:
return T(n)
else:
return Tk(T(n),k-1)

def Xk(n,k):
return Tk(n,k)%2

def log2(n):
i=0
while 2**i < n:
i += 1
return i

def Ek(n):
e=[n%2]
e.extend([Xk(n,k) for k in range(1,log2(n))])
return e

def Eknum(n):
e=Ek(n)
return sum([int(e[i])*2**(len(e)-i-1) for i in range(len(e))])

def b(n):
return n>>(log2(n)-95)

def alg1(n):
ao=0
while True:
atmp = bin(b(n+ao)^Eknum(n+ao))[2:97]
s=0
for i in range(len(atmp)):
p = 2**(len(atmp)-i-1)
s = s + int(atmp[i])*p
a=(s+ao)%2**128
ao=a
yield a

x=2**95+1
c=alg1(x)
print([c.__next__() for i in range(10)])

But it generate:

[29710560942849126597578981376, 66848762121410534844552708098, 93309730461135538220521488396, 121424509322093354307488317616, 143747777928459837504378375029, 16666801032665883829202388206
5, 192453271774632714178135801711, 221461690903603324550112302767, 254096162423695261219320943435, 290809942883798689978404902290]

while my code is giving this:

26409387504754779197847983445
6602346876188694799461995862
36312907819037821397040977237
31361147661896300297444480342
30948500982134506872478105599
19084908938982945904694831779
20619438779347115203788537830
30963008091969882422574579680
26590524890060371135858124948
11244010018346911751297530592

osobli...@gmail.com

unread,
Nov 18, 2021, 5:50:24 AM11/18/21
to
There was mistake in my code (in generator(a,n) the bracket after xoring was missing). New code:

https://pastebin.com/6WCz23yJ

And there was still problem with float here (and again code didn't work properly for big numbers):

def T(n):
return (n*3**(n%2)+n%2)/2

It can be solved by:

def T(n):
return ((n*3**(n%2)+n%2) >> 1)

What's more, because of this:

def Ek(n):
e=[n%2]
e.extend([Xk(n,k) for k in range(1,log2(n))])
return e

Eknum has one bit to much (because we are adding one bit by e=[n%2]). It has to be:

def Ek(n):
e=[n%2]
e.extend([Xk(n,k) for k in range(1,log2(n)-1)])
return e

Code:

https://pastebin.com/ScBEEkUe

Now my generator gives:

10728813673806629049125743275
43534224714869206333952535195
83027950690404185381775984360
85695704988762563500290700319
109284597327138005024516384409

And yours:

10728813673806629049125743275
43534224714869206333952535195
61570323342790927283524497934
99584477629507392555371042387
107685917320496578600785099066

I have no idea why results are different after 2 iterations.

osobli...@gmail.com

unread,
Nov 18, 2021, 6:17:02 AM11/18/21
to
With bigger numbers than 2**95+1 iterations are completely different. I think the mistake is in:

atmp = bin(b(n+ao)^Eknum(n+ao))[2:97]

It Eknum(n+ao) could cut least significant bits before xoring, because we want number Eknum(n+ao) composed of 95 most significant bits. If we not cut them first it will xor using 95 least significant bits, because this is how xoring works. Am I right?

wizzofozz

unread,
Nov 18, 2021, 5:17:39 PM11/18/21
to
Op 18-11-2021 om 12:17 schreef osobli...@gmail.com:
> czwartek, 18 listopada 2021 o 11:50:24 UTC+1 osobli...@gmail.com napisał(a):
>> There was mistake in my code (in generator(a,n) the bracket after xoring was missing). New code:
>>
>> https://pastebin.com/6WCz23yJ
>> What's more, because of this:
>> def Ek(n):
>> e=[n%2]
>> e.extend([Xk(n,k) for k in range(1,log2(n))])
>> return e
>> Eknum has one bit to much (because we are adding one bit by e=[n%2]). It has to be:
>>
>> def Ek(n):
>> e=[n%2]
>> e.extend([Xk(n,k) for k in range(1,log2(n)-1)])
>> return e
>>

I agree with e[0]=n%2, but I disagree with log2(n)-1. Note that my
version rounds log2 up, so that may be a source of confusion. Also note
that I start from 1 in range(1,log2(n)).

The version I have gives the same result as in the paper.
Ek(26)
[0, 1, 0, 0, 1]

>>
>> I have no idea why results are different after 2 iterations.
>
> With bigger numbers than 2**95+1 iterations are completely different. I think the mistake is in:
>
> atmp = bin(b(n+ao)^Eknum(n+ao))[2:97]
>
> It Eknum(n+ao) could cut least significant bits before xoring, because we want number Eknum(n+ao) composed of 95 most significant bits. If we not cut them first it will xor using 95 least significant bits, because this is how xoring works. Am I right?
>

Ok, I see your point. Then it may be better to forget about the
Ek-vector as a number (so no more Eknum) and only interpret it as a vector.
Now I xor Ek=[X0,X1,X2,...,X94] with b(n+ao)=[b94,b93,b92,...,b0]. But I
am not sure. The paper is not explicit on this. And we don't have any
test vectors, so we don't really know what to work towards.

Here is my final version, as I interpret the description of alg1. Sorry
that it is still in python2 (so you may have to rewrite a bit to make it
work). I skipped the final step where you have to do Ek(n+a0)Ek(n+a1)...

If you post the broken seeds I can test again. Btw, the paper considers
seeds > 2**95.

Ozz

#!/bin/python

def T(n):
return (n*3**(n%2)+n%2)/2

def Tk(n,k):
if k==1:
return T(n)
else:
return Tk(T(n),k-1)


def Xk(n,k):
return Tk(n,k)%2


def log2(n): # rounds up
i=0
while 2**i < n:
i += 1
return i

def Ek(n):
e=[n%2]
e.extend([Xk(n,k) for k in range(1,log2(n))])
return e

def b(n):
return n>>(log2(n)-95)


def alg1(n):
ao=0
while True:
bv=[int(i) for i in bin(b(n+ao))[2:]]
ekv=Ek(n+ao)[:95]
av=[x^y for (x,y) in zip(bv,ekv)]
s=0
for i in range(len(av)):
s = s + av[i]*2**(len(av)-i-1)
a=(s+ao)%(2**128)
ao=a
yield a


x=2**95+1
c=alg1(x)
for i in range(50):
print c.next()





wizzofozz

unread,
Nov 18, 2021, 5:33:14 PM11/18/21
to
Op 18-11-2021 om 23:17 schreef wizzofozz:
> Op 18-11-2021 om 12:17 schreef osobli...@gmail.com:
>> czwartek, 18 listopada 2021 o 11:50:24 UTC+1 osobli...@gmail.com
>> napisał(a):
>>> What's more, because of this:
>>> def Ek(n):
>>> e=[n%2]
>>> e.extend([Xk(n,k) for k in range(1,log2(n))])
>>> return e
>>> Eknum has one bit to much (because we are adding one bit by e=[n%2]).
>>> It has to be:
>>>
>>> def Ek(n):
>>> e=[n%2]
>>> e.extend([Xk(n,k) for k in range(1,log2(n)-1)])
>>> return e
>>>
>
> I agree with e[0]=n%2, but I disagree with log2(n)-1. Note that my
> version rounds log2 up, so that may be a source of confusion. Also note
> that I start from 1 in range(1,log2(n)).
>
> The version I have gives the same result as in the paper.
> Ek(26)
> [0, 1, 0, 0, 1]
>

Hmm, the paper says: "Let n be a positive integer and k be the
smallest positive integer such that n<2**k".

So if n == 32, then k should be 6. My version uses k = 5, so I guess
that is not correct (so the code I just posted is probably wrong there).

For 26 I still believe it's correct.

Maybe you could check that in your version.

Ozz

osobli...@gmail.com

unread,
Nov 18, 2021, 8:26:53 PM11/18/21
to
Now we have the same results. Note that the output is binary sequence:

"We obtain a binary sequence by concatenating vectors Ek(n+a0), Ek(n+a1),Ek(n+a2), ... together."

And you return a_i. Anyway, that doesn't matter. If a_i will fall into short cycle, Ek(n+a_i) also will.


So broken seeds are every numbers bigger than 2^95 of the form 2**x-1. For example for 2**96-1 we get:

0,0,0,...

The same for other such numbers. Problem will occur also for Ek(n+a_i) - it has to, by definition. That shows the proof in paper is wrong. Authors are not aware of the exceptions, nor does estimate number of exceptions. We can not be sure that there are no other short cycles (we can imagine the existence of such - the Collatz sequences can generate such vectors that they loop the results in many ways, we don't know). The evidence in paper does not provide us with certainty on this topic and the best evidence of this are shown by broken seeds.

wizzofozz

unread,
Nov 19, 2021, 12:50:00 PM11/19/21
to
Op 19-11-2021 om 02:26 schreef osobli...@gmail.com:
> Now we have the same results. Note that the output is binary sequence:
>
> "We obtain a binary sequence by concatenating vectors Ek(n+a0), Ek(n+a1),Ek(n+a2), ... together."
>
> And you return a_i. Anyway, that doesn't matter. If a_i will fall into short cycle, Ek(n+a_i) also will.
>

Yes, that's why I wrote two posts ago:

"I skipped the final step where you have to do Ek(n+a0)Ek(n+a1)...".

>
> So broken seeds are every numbers bigger than 2^95 of the form 2**x-1. For example for 2**96-1 we get:
>
> 0,0,0,...
>
> The same for other such numbers. Problem will occur also for Ek(n+a_i) - it has to, by definition. That shows the proof in paper is wrong. Authors are not aware of the exceptions, nor does estimate number of exceptions. We can not be sure that there are no other short cycles (we can imagine the existence of such - the Collatz sequences can generate such vectors that they loop the results in many ways, we don't know). The evidence in paper does not provide us with certainty on this topic and the best evidence of this are shown by broken seeds.
>

Ok, indeed I get the 0's, even with my 'fix' of one post ago (do you
agree with that fix? because it may be important).

I might take a look this weekend to see if I can break the cycle by
trying other variants of the implementation which could also make sense
according to the description.

Ozz

osobli...@gmail.com

unread,
Nov 19, 2021, 2:50:01 PM11/19/21
to
piątek, 19 listopada 2021 o 18:50:00 UTC+1 wizzofozz napisał(a):
> Op 19-11-2021 om 02:26 schreef osobli...@gmail.com:
> > Now we have the same results. Note that the output is binary sequence:
> >
> > "We obtain a binary sequence by concatenating vectors Ek(n+a0), Ek(n+a1),Ek(n+a2), ... together."
> >
> > And you return a_i. Anyway, that doesn't matter. If a_i will fall into short cycle, Ek(n+a_i) also will.
> >
> Yes, that's why I wrote two posts ago:
>
> "I skipped the final step where you have to do Ek(n+a0)Ek(n+a1)...".
> >
> > So broken seeds are every numbers bigger than 2^95 of the form 2**x-1. For example for 2**96-1 we get:
> >
> > 0,0,0,...
> >
> > The same for other such numbers. Problem will occur also for Ek(n+a_i) - it has to, by definition. That shows the proof in paper is wrong. Authors are not aware of the exceptions, nor does estimate number of exceptions. We can not be sure that there are no other short cycles (we can imagine the existence of such - the Collatz sequences can generate such vectors that they loop the results in many ways, we don't know). The evidence in paper does not provide us with certainty on this topic and the best evidence of this are shown by broken seeds.
> >
> Ok, indeed I get the 0's, even with my 'fix' of one post ago (do you
> agree with that fix? because it may be important).

Yes, it works properly for me.

> I might take a look this weekend to see if I can break the cycle by
> trying other variants of the implementation which could also make sense
> according to the description.

I think the only option is to to interpret differently Ek(n+a_i)[:95]. But in this case 2^x-1 gives just Ek = 1,1,1,...,1,1,1. No matter how we would read bits (first is most significant or least singificant), how we enumerate them and do we take first or last 95 bits - it always gives the same number.

osobli...@gmail.com

unread,
Nov 19, 2021, 2:56:00 PM11/19/21
to
By the way I plan to contact the author. I hope he will write back to me. However, I wanted to check if I was wrong. Especially since some things in the algorithm can be confusing.

wizzofozz

unread,
Nov 20, 2021, 4:58:18 AM11/20/21
to
Op 19-11-2021 om 20:49 schreef osobli...@gmail.com:
> piątek, 19 listopada 2021 o 18:50:00 UTC+1 wizzofozz napisał(a):.
>
>> I might take a look this weekend to see if I can break the cycle by
>> trying other variants of the implementation which could also make sense
>> according to the description.
>
> I think the only option is to to interpret differently Ek(n+a_i)[:95]. But in this case 2^x-1 gives just Ek = 1,1,1,...,1,1,1. No matter how we would read bits (first is most significant or least singificant), how we enumerate them and do we take first or last 95 bits - it always gives the same number.
>

I think you are right.
Interesting that Tk(2**x-1) only returns 1's for the first 2log(2**x-1)
positions. After that it seems to behave more random.

But anyway, I agree with you that we cannot break out of the cycle of
0's without 'major' changes to alg1.

So it seems that you found a counter example to their proof.
I'm interested in the reaction of the author if he responds to your
message. I think that if there is some misunderstanding, they need to
fix their paper to make it more precise/clear.
Otherwise, good for you for finding this.

Ozz

osobli...@gmail.com

unread,
Nov 20, 2021, 9:16:19 AM11/20/21
to
> Interesting that Tk(2**x-1) only returns 1's for the first 2log(2**x-1)
> positions.

There is elementary proof of that. In general a number of the form 2^a*b-1 always gives a number of the form 3^a*b-1 after "a" iterations of Collatz function.

We can ask - can we have a cycle, that:

(3^a*b-1)/2^c = 2^a*b-1

Because of course 3^a*b-1 is even, so after that we divide by 2 (and it can be several dividings). This would be the so-called 1-cycle. Steiner (1977) proved that there is no 1-cycle other than the trivial (1,2,...).

> After that it seems to behave more random.

Like Collatz sequences in general. Hence we have an estimate of the average length of the sequence after which the sequence reaches 1:

d(n) ~ 2/ln(4/3) * ln(n)

If we assume that the divisions (x/2) and multiplications (1.5x+0.5) in Collatz sequences are alternating, completely random we can easily obtain such a formula for the average length of the sequence. And this formula works very well fo all numbers. It was used by the authors of this publication:

https://www.researchgate.net/publication/51909572_A_Conjecture_on_the_Collatz-Kakutani_Path_Length_for_the_Mersenne_Primes

They tried to estimate deviations of the length of Collatz sequences for Mersenne numbers to find Mersenne primes. Of course, they considered that each number 2^a-1 gives 3^a-1 after "a" steps and then sequence starting to behave randomly.

> But anyway, I agree with you that we cannot break out of the cycle of
> 0's without 'major' changes to alg1.

And we can imagine other, more complicated, bad generator behaviors, other short cycles. They seem to be unlikely, but I don't think we can be sure they won't occur.

> So it seems that you found a counter example to their proof.
> I'm interested in the reaction of the author if he responds to your
> message. I think that if there is some misunderstanding, they need to
> fix their paper to make it more precise/clear.
> Otherwise, good for you for finding this.

I think it cannot be fixed easy. Even if we add some xoring or bit mixing there - we can not be sure that the behavior of the Collatz sequences will not work just against our countermeasures, by a chance. I created my own generators based on the Collatz sequences and their generalizations and faced the same problems. And we don't have a good theory to solve them. Therefore, the design of such generators must be very thoughtful.


Reply all
Reply to author
Forward
0 new messages