Emanuel Landeholm - cp's OEIS frontend

A362940 Consider the Collatz trajectory from n to 1, assuming the Collatz conjecture is true. Then a(n) = number of terms in the trajectory that are greater than 1 and congruent to 1 mod 3. If n never reaches 1, set a(n) = -1.

0, 0, 3, 1, 2, 3, 9, 1, 10, 3, 7, 3, 5, 9, 8, 2, 6, 10, 11, 3, 3, 8, 7, 3, 13, 5, 61, 10, 9, 8, 59, 2, 14, 7, 6, 10, 12, 11, 18, 4, 60, 3, 17, 8, 8, 8, 57, 3, 14, 13, 12, 6, 5, 61, 62, 10, 18, 10, 17, 8, 10, 59, 58, 3, 15, 14, 15, 7, 7, 7, 56, 10, 64, 12, 7, 12

Offset: 1

N. J. A. Sloane, Sep 11 2023, suggested by a sequence submitted by Emanuel Landeholm on Sep 10 2023 but later withdrawn, which had a somewhat different definition and contained errors

nonn

The terms in the trajectory counted by a(n) might be called "branch points", since they are exactly the numbers that can be reached in more than one way under the Collatz map. So a(n) is a measure of the "Collatz complexity" of n. The term (with a slightly different definition) was suggested by Emanuel Landeholm.

			The Collatz trajectory of 7 is 7 22 34 17 52 26 13 40 20 10 5 16 8 4 2 1, which contains 9 terms > 1 and 1 mod 3, so a(7) = 9.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A006577, A008908.

Table[Count[NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, k, # > 1 &], ?(And[# != 1, Mod[#, 3] == 1] &)] , {k, 100}] (* _Michael De Vlieger, Sep 11 2023 *)

A346036 Number of swaps needed to return the recursive transform T(k) = concatenate(reverse(k), len(k) + 1) to the tuple 1, 2, ..., n.

Original entry on oeis.org

0, 0, 1, 2, 2, 4, 5, 4, 6, 8, 7, 10, 10, 10, 13, 12, 12, 14, 17, 16, 18, 18, 17, 22, 22, 20, 25, 24, 24, 28, 29, 24, 26, 32, 31, 34, 32, 32, 35, 38, 36, 40, 35, 40, 40, 40, 39, 44, 46, 42, 49, 50, 44, 52, 51, 52, 52, 54, 51, 54, 58, 56, 59, 54, 54, 64, 61, 60

Offset: 1

Emanuel Landeholm, Jul 02 2021

nonn

			For n=7, the T transforms give tuple 6,4,2,1,3,5,7 (triangle A220073 row 7) which requires a(7) = 5 swaps to return to 1,2,3,4,5,6,7.

Cf. A220073.

a(n) = my(h=n>>1); n - #permcycles(vectorsmall(n,i, abs(2*i-n) + (i<=h))); \\ Kevin Ryde, Jul 23 2021

def swaps(l, start = 0):
  if len(l) == 0:
    return 0
  n = start + 1
  if l[0] != n:
    for i, x in enumerate(l):
      if x == n:
        l[0], l[i] = l[i], l[0]
        return 1 + swaps(l[1:], n)
    else:
      raise
  else:
    return swaps(l[1:], n)
def T(l):
  n = len(l)
  l.reverse()
  l.append(n + 1)
  return l
if _name_ == "_main_":
  l = [ ]
  for n in range(1, 100):
    l = T(l)
    n_swaps = swaps(l[:])
    print("{}, ".format(n_swaps), end="")

A340265 a(n) = n + 1 - a(phi(n)).

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 3, 6, 5, 8, 4, 10, 4, 10, 10, 11, 7, 14, 6, 15, 12, 15, 9, 19, 11, 17, 14, 19, 11, 25, 7, 22, 19, 24, 17, 27, 11, 25, 21, 30, 12, 33, 11, 30, 27, 32, 16, 38, 17, 36, 30, 34, 20, 41, 26, 38, 31, 40, 20, 50, 12, 38, 37, 43, 28, 52, 16, 47, 40, 52, 20, 54, 20, 48

Offset: 1

Emanuel Landeholm, Jan 03 2021

Since phi(n) < n, a(n) only depends on earlier values a(k), k < n. This makes the sequences computable using dynamic programming. The motivation for the "+ 1" is that without it the sequence becomes half-integer as a(1) would equal 1/2.

1 <= a(n) <= n. Proof: Suppose 1 <= a(k) <= k for all k < n. Then a(k + 1) = k + 1 + 1 - a(phi(k + 1)). As 1 <= a(phi(k)) <= k we have 2 <= k + 1 + 1 - k <= k + 1 + 1 - a(phi(k + 1)) = a(k + 1) <= k + 1.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A053478.

f:= proc(n) option remember; n+ 1 - procname(numtheory:-phi(n)); end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Jan 06 2021

Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi@#]], Listable]@Range[70]

first(n) = {my(res = vector(n)); res[1] = 1; for(i = 2, n, res[i] = i + 1 - res[eulerphi(i)]); res} \\ David A. Corneth, Jan 03 2021

from sympy import totient as phi
N = 100
# a(n) = n + 1 - a(phi(n)), n > 0, a(0) = 0
a = [ 0 ] * N
# a(1) = 1 + 1 - a(phi(1)) = 2 - a(1) => 2 a(1) = 2 => a(1) = 1
# a(n), n > 1 computed using dynamic programming
a[1] = 1
for n in range(2, N):
  a[n] = n + 1 - a[phi(n)]
print(a[1:])

from sympy import totient as phi
def a(n): return 1 if n==1 else n + 1 - a(phi(n))
print([a(n) for n in range(1, 100)]) # Michael S. Branicky, Jan 03 2021

a(n) = n + Sum_{k=1..floor(log_2(n))} (-1)^k*(phi^k(n) - 1), where phi^k(n) is the k-th iterate of phi(n). - Ridouane Oudra, Oct 10 2023

A290032 a(0)=0; for n > 0, a(n) is the sum of the partial sums of binary digits of a(n-1) + 1, starting from the least significant digit, and given weights 1, 2, 2^2, etc.

Original entry on oeis.org

0, 1, 2, 5, 10, 37, 154, 1125, 9114, 121957, 1188762, 19782757, 449979290, 7603084389, 147015738266, 4800786586725, 197509352924058, 6557890088131685, 254650888299357082, 7815799643948571749, 315002221645968581530

Offset: 0

Emanuel Landeholm, Jul 18 2017

			a(4) is computed as follows: a(3) + 1 = 6 = 110_2; the partial sums of digits and their weights are (0,1), (0+1,2), and (0+1+1,4), so the sum of partial sums is 0*1 + 1*2 + 2*4 = 10.

PartialSums = Function[Accumulate[Reverse[IntegerDigits[#, 2]]]]
NestList[Total[# Power[2, Range[0, Length[#] - 1]]] &[PartialSums[1 + #]] &, 0, 20]

cp's OEIS Frontend

User: Emanuel Landeholm

A362940 Consider the Collatz trajectory from n to 1, assuming the Collatz conjecture is true. Then a(n) = number of terms in the trajectory that are greater than 1 and congruent to 1 mod 3. If n never reaches 1, set a(n) = -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A346036 Number of swaps needed to return the recursive transform T(k) = concatenate(reverse(k), len(k) + 1) to the tuple 1, 2, ..., n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Python

A340265 a(n) = n + 1 - a(phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A290032 a(0)=0; for n > 0, a(n) is the sum of the partial sums of binary digits of a(n-1) + 1, starting from the least significant digit, and given weights 1, 2, 2^2, etc.

Views

Author

Keywords

Examples

Programs

Mathematica