[quote]A modified Collatz sequence of integers is obtained from a starting value a1 in the following way:
an+1 = an/3 if an is divisible by 3. We shall denote this as a large downward step, “D”.
an+1 = (4an + 2)/3 if an divided by 3 gives a remainder of 1. We shall denote this as an upward step, “U”.
an+1 = (2an - 1)/3 if an divided by 3 gives a remainder of 2. We shall denote this as a small downward step, “d”.
The sequence terminates when some an = 1.
Given any integer, we can list out the sequence of steps.
For instance if a1=231, then the sequence {an}={231,77,51,17,11,7,10,14,9,3,1} corresponds to the steps “DdDddUUdDD”.
Of course, there are other sequences that begin with that same sequence “DdDddUUdDD…”.
For instance, if a1=1004064, then the sequence is DdDddUUdDDDdUDUUUdDdUUDDDUdDD.
In fact, 1004064 is the smallest possible a1 106 that begins with the sequence DdDddUUdDD.
What is the smallest a1 1015 that begins with the sequence “UDDDUdddDDUDDddDdDddDDUDDdUUDd”?[/quote]
Problem nastręczał trudności, bruteforce zupełnie odpada. A więc do dzieła:
Zauważamy że sekwencja musi rozpocząć się od U czyli liczba musi byc podzielna przez 3. Jezeli zaczniemy sobie wypisywac wszystkie liczby po kolei ktore spelniaja warunek ze zaczyna sie od np “UD”, to zauwazymy ze odleglosc miedzy tymi liczbami jest stałą. Potrzebujemy znaleźć tylko stałą która dzieli liczby zaczynające się od żądanego ciągu ORAZ liczbę początkową.
[code=ruby]#sprawdzenie czy liczba x wygeneruje ciąg zaczynający się od dest
def coll(x,s,dest)
return false if s.length > dest.length || (s.length > 0 && (s[-1] != dest[s.length-1]))
return true if s == dest
case x % 3
when 0
return coll(x/3,s+“D”,dest)
when 1
return coll((4x+2)/3, s + “U”,dest)
else
return coll((2x-1)/3, s + “d”,dest)
end
end
#docelowy ciąg
destiny =“UDDDUdddDDUDDddDdDddDDUDDdUUDd”
start = 1 #zaczynamy od liczby 1
diff = 0 #zmienna pomocnicza
inc = 1 #w tej chwili zwiększamy o 1, ale wewnątrz pętli inkrementor będzie się zwiększać, na przykład z U wyznaczy ze inc = 3, a potem przejdzie do UD i wyznaczy, że inc =9
tmp = “” #zmienna pomocnicza
destiny.split("").each do |x|
tmp += x #w kazdym kroku szukamy coraz większego podciągu UDDDU…
i = start
found = false
while true
if coll(i,"",tmp)
if !found
found = true
start = i
else
diff = i - start
break
end
end
i+=inc
end
inc = diff
end
while start < 10**15
start += diff
end
puts start[/code]