73 views

Skip to first unread message

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.

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

Nov 17, 2021, 5:55:17 AM11/17/21

to

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.

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

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.

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)]

Nov 17, 2021, 6:14:13 PM11/17/21

to

<generator object <genexpr> at 0x000001E8189B54A0>

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.

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

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."

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.

Nov 17, 2021, 11:04:32 PM11/17/21

to

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.

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

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

Nov 18, 2021, 3:23:27 AM11/18/21

to

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.

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

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.

Nov 18, 2021, 6:17:02 AM11/18/21

to

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

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()

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

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.

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

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.

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.

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

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

Search

Clear search

Close search

Google apps

Main menu