Implementation of PRNG based on the Collatz conjecture
73 views
Skip to first unread message
osobli...@gmail.com
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.
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
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.
> In paper "Pseudo-random number generators based on the Collatz conjecture":
>
> https://sci-hub.se/10.1007/s41870-019-00307-9
--
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
Nov 17, 2021, 5:55:17 AM11/17/21
to
Richard Heathfield
Nov 17, 2021, 6:07:45 AM11/17/21
to
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
Nov 17, 2021, 6:20:39 AM11/17/21
to
You could be able to download it from here:
https://altosharepdf.com/share/5ff2ee173ed04e4ab6a1879b6aa444a8
https://altosharepdf.com/share/5ff2ee173ed04e4ab6a1879b6aa444a8
Richard Heathfield
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.
> You could be able to download it from here:
>
> https://altosharepdf.com/share/5ff2ee173ed04e4ab6a1879b6aa444a8
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
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)]
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
Nov 17, 2021, 6:14:13 PM11/17/21
to
<generator object <genexpr> at 0x000001E8189B54A0>
osobli...@gmail.com
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.
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)
e.extend([Xk(n,k) for k in range(1,log2(n)+1)])
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
Nov 17, 2021, 8:53:17 PM11/17/21
to
> 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]
> 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:
>
> 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))])
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
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
> 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).
afterthought in my limited spare time just imagine what I could do if I
really devoted myself to it."
osobli...@gmail.com
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.
> 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.
osobli...@gmail.com
Nov 17, 2021, 11:04:32 PM11/17/21
to
osobli...@gmail.com
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
Nov 18, 2021, 1:41:43 AM11/18/21
to
Op 18-11-2021 om 05:07 schreef osobli...@gmail.com:
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
> 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
>> 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:
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.
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.
>
Regarding your remark about the generator next(); at my end it just
seems to work. I'm using python2.7.
Ozz
wizzofozz
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
Nick following it :-)
Ozz
osobli...@gmail.com
Nov 18, 2021, 3:23:27 AM11/18/21
to
osobli...@gmail.com
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.
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
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):
return sum([int(e[i])*2**(len(e)-i-1) for i in range(len(e))])
def b(n):
return n>>(log2(n)-95)
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
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]
while 2**i < n:
i += 1
return i
def Ek(n):
e.extend([Xk(n,k) for k in range(1,log2(n))])
return e
def Eknum(n):
e=Ek(n)
return e
def Eknum(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:
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)
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
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.
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
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
Nov 18, 2021, 6:17:02 AM11/18/21
to
atmp = bin(b(n+ao)^Eknum(n+ao))[2:97]
wizzofozz
Nov 18, 2021, 5:17:39 PM11/18/21
to
Op 18-11-2021 om 12:17 schreef osobli...@gmail.com:
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
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)
print c.next()
> 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
>> 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
>> 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
>>
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?
>
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
i=0
while 2**i < n:
i += 1
return i
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
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:]]
return n>>(log2(n)-95)
def alg1(n):
ao=0
while True:
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):
yield a
x=2**95+1
c=alg1(x)
print c.next()
wizzofozz
Nov 18, 2021, 5:33:14 PM11/18/21
to
Op 18-11-2021 om 23:17 schreef wizzofozz:
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
> 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):
>> 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
>>> 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]
>
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
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.
"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
Nov 19, 2021, 12:50:00 PM11/19/21
to
Op 19-11-2021 om 02:26 schreef osobli...@gmail.com:
"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
> 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:
>
> "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.
>
"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.
>
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
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.
> 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.
osobli...@gmail.com
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
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):.
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
> 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.
>> 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.
>
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
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.
> positions.
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.
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.
> 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.
Reply all
Reply to author
Forward
0 new messages