ncats puzzle 2 backend: Collatz sibblings

collatz_tree64_final.jl

import JSON

function init(mytype)	
	# vector of vectors of whatever type is passed in
	vv = Vector{Vector{mytype}}(64)
	vv[1]=[mytype(1)]  # 
	vv[2]=[mytype(2)]  # even double  -1,/3 == .333 not int
	vv[3]=[mytype(4)]  # even double  -1,/3 == 1 is previously done
	vv[4]=[mytype(8)]  # even double  -1,/3 == 7/3 not int
	vv[5]=[mytype(16)] # even double  -1,/3 == 5 (start a new chain @ 5)  
	vv[6]=[mytype(5), mytype(32)]  
	return vv
end

function compute!(mytype, store, start::Int64, stop::Int64)
	zro=mytype(0)
	one=mytype(1)
	two=mytype(2)
	thr=mytype(3)
	#fivmsk = 0x55555555
	#aeemsk = 0xAAAAAAAA
	for level in start:stop
		store[level]=Vector()
		for n in store[level-1]
			push!(store[level], n*two) 
			
			# bit twiddle to find divisable by three?
			# if 0 == count_ones(n& fivmsk)+count_ones(n& aeemsk)<<1 
			if(zro == ((n-one)%thr))
				z=mytype((n-one)//thr)
				if z > zro && (z&one==one)
					push!(store[level], z)
				end
			end
		end
		# sort not needed to produce, but may help for checking and retrivial
		sort!(store[level]) 
	end
	return store
end



function report(store, lim)	
	JSON.print(store)
end

# call
lim = 64
mtyp = UInt64
# other types of integer storage to test include 
# Int64 Int128 UInt128 BigInt
# reason: I was not convinced all "excursions" along a path would be <= 2^64
report(compute!(mtyp, init(mtyp), 7, lim), lim)

# returuns in < 5 seconds