8
\$\begingroup\$

This challenge is based on some new findings related to the Collatz conjecture and designed somewhat in the spirit of a collaborative polymath project. Solving the full conjecture is regarded as extremely difficult or maybe impossible by math/number theory experts, but this simpler task is quite doable and there is many examples of sample code. In a best case scenario, new theoretical insights might be obtained into the problem based on contestants entries/ ingenuity/ creativity.

The new finding is as follows: Imagine a contiguous series of integers [ n1 ... n2 ] say m total. Assign these integers to a list structure. Now a generalized version of the Collatz conjecture can proceed as follows. Iterate one of the m (or fewer) integers in the list next based on some selection criteria/algorithm. Remove that integer from the list if it reaches 1. Clearly the Collatz conjecture is equivalent to determining whether this process always succeeds for all choices of n1, n2.

Here is the twist, an additional constraint. At each step, add the m current iterates in the list together. Then consider the function f(i) where i is the iteration number and f(i) is the sum of current iterates in the list. Look for f(i) with a particular "nice" property.

The whole/ overall concept is better/ more thoroughly documented here (with many examples in ruby). The finding is that fairly simple strategies/ heuristics/ algorithms leading to "roughly monotonically decreasing" f(i) exist and many examples are given on that page. Here is one example of the graphical output (plotted via gnuplot):

So here is the challenge: Use varations on the existing examples or entirely new ideas to build a selection algorithm resulting in a f(i) "as close to monotonically decreasing as possible". Entrants should include a graph of f(i) in their submission. Voters can vote based on that graph & the algorithmic ideas in the code.

The contest will be based on n1 = 200 / n2 = 400 parameters only! (the same on the sample page.) But hopefully the contestants will explore other regions and also attempt to generalize their algorithms.

Note, one tactic that might be very useful here are gradient descent type algorithms, or genetic algorithms.

Can discuss this all further in chat for interested participants.

For some ref, another codegolf Collatz challenge: Collatz Conjecture (by Doorknob)

\$\endgroup\$
12
  • 5
    \$\begingroup\$ Capitalization please! \$\endgroup\$
    – TheDoctor
    May 1, 2014 at 22:28
  • 1
    \$\begingroup\$ Why are people voting to close? It's nice to have non-stereotypical questions! I the problem too much thinking/reading involved in understanding the question?! \$\endgroup\$
    – Mau
    May 2, 2014 at 13:38
  • 2
    \$\begingroup\$ iterate here means "advance to next 'iterate' in the Collatz sequence for that integer" \$\endgroup\$
    – vzn
    May 2, 2014 at 20:05
  • 1
    \$\begingroup\$ It looks like the example you've posted will be hard to beat... :) \$\endgroup\$
    – apnorton
    May 6, 2014 at 21:58
  • 1
    \$\begingroup\$ @vzn I can't promise a submission anytime soon, as I'm headed on vacation this weekend after school ends, and things are kinda hectic right now. However, I will certainly experiment with this--after all, this is a novel approach to a problem I find very intriguing. :) \$\endgroup\$
    – apnorton
    May 6, 2014 at 23:02

2 Answers 2

4
\$\begingroup\$

I wrote some code in Python 2 to run algorithms for this challenge:

import matplotlib.pyplot as plt

def iterate(n):
    return n*3+1 if n%2 else n/2
def g(a):
    ##CODE GOES HERE
    return [True]*len(a)
n1=input()
n2=input()
a=range(n1,n2+1)
x=[]
y=[]
i=0
while any(j>1 for j in a):
    y.append(sum(a))
    x.append(i)
    i+=1
    b=g(a)
    for j in range(len(a)):
        if b[j]:
            a[j]=iterate(a[j])
plt.plot(x,y)
plt.show()

g(x) takes the list of values and returns a list of bools for whether each one should be changed.

That includes the first thing I tried, as the line right after the comment, which was iterating all of the values in the list. I got this:

Attempt 1

It doesn't look close to monotonic, so I tried iterating only values that would decrease the sum, if there are any, iterating the ones that would increase it least otherwise:

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m=[n[i]-a[i] for i in range(l)]
return [m[i]==min(m) for i in range(l)]

Unfortunately, that doesn't terminate (at least for n1=200, n2=400). I tried keeping track of values I'd seen before by initializing c=set():

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m={i:n[i]-a[i] for i in range(l)}
r=[i for i in m if m[i]==min(m.values())]
while all([a[i] in c for i in r]) and m != {}:
    m={i:m[i] for i in m if a[i] not in c}
    r+=[i for i in m.keys() if m[i]==min(m.values())]
for i in r:
    c.add(a[i])
return [i in r for i in range(l)]

That doesn't terminate either, though.

I haven't tried anything else yet, but if I have new ideas, I'll post them here.

\$\endgroup\$
1
  • \$\begingroup\$ +1 thx for your interest & reviving the challenge. this is not very good for performance but you get the acceptance anyway, my small gesture of thx :) ... also others interested plz feel free to chat about it or invite me into chat to further discuss \$\endgroup\$
    – vzn
    Jan 23, 2015 at 21:02
2
\$\begingroup\$

Python 3

My main idea was to add each numbers Collatz sequence to the f(i) function individually in a way that it minimizes the total increasing of f(i). The resulting function isn't strictly decreasing but it has a nice structure (in my opinion :)). The second graph was created with longer interval for f(i) and slightly different punishment function. Code on Gist.

Collatz1 Collatz2

When using the (3*n+1)/2 rule instead the 3*n+1 one the algorithm produces a completely monotonic f(i)! I'm sure this modification could make vzn's graphs a lot smoother too. The second graph was created with longer interval for f(i). Code on Gist.

Collatz3 Collatz4

Both results are similar for bigger [n,2*n] ranges.

\$\endgroup\$
8
  • \$\begingroup\$ 2nd two are novel/ great, best outside entries so far! a completely monotonic decrease is something like a breakthrough! if you can show it works on increasingly larger starting iterates in "similar way", that is a actual proof strategy candidate...! \$\endgroup\$
    – vzn
    Jan 25, 2015 at 17:03
  • \$\begingroup\$ @vzn With some modification strictly monotonic f seems to be achievable. Even if my current algorithm fails there is considerable space for improvement. I will let it run and see if it fails for some n (over 200). Strict monotony is stronger the the Collatz conjecture so I might pass on that for now. :) Do your functions work well with the (3n+1)/2 rule? Why don't you use that? \$\endgroup\$
    – randomra
    Jan 25, 2015 at 19:12
  • \$\begingroup\$ @vzn So many ideas... The main holdback is the relevant xkcd :). The monotonic decrease seems to hold. A [1,n] range might be more interesting because there we could also ask (if the monotony holds) whether we can create an [1,n+1] by not modifying the [1,n] one and adding the n+1 sequence to it. \$\endgroup\$
    – randomra
    Jan 25, 2015 at 21:59
  • \$\begingroup\$ so nice to see some shared inspiration! a proof strategy could work either way, eg in constant-sized "blocks". from experiments on the cited pg, various strategies tend to "break" for larger n. more detailed description of your algorithm in words would be great. \$\endgroup\$
    – vzn
    Jan 25, 2015 at 23:15
  • \$\begingroup\$ fyi ported this to ruby & did some basic experiments, graphed results here. the code seems to have some small dependence on nondeterminism in the sort but maybe not for larger n. \$\endgroup\$
    – vzn
    Feb 28, 2015 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.