A256757 -id:A256757 - cp's OEIS frontend

A256758 Position of first appearance of n in A256757.

1, 2, 3, 7, 19, 47, 163, 487, 1307, 2879, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 344373773, 688747547, 3486784401

Offset: 0

Ivan Neretin, Apr 09 2015

Smallest number m such that the trajectory of m under iteration of A007733 takes n steps to reach the fixed point.

The terms a(1)..a(9) are primes. The next eight terms are powers of 3, so that for n=10..17, a(n)=3^(n-1), but this apparently established pattern breaks at a(18), which is again a prime.

Cf. A007733, A007755 (similarly built upon the totient function), A173927 (similarly built upon the Carmichael lambda function), A256757.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a256758 = (+ 1) . fromJust . (`elemIndex`  a256757_list)
-- Reinhard Zumkeller, Apr 13 2015

A007733 = Function[n, MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]];
A256757 = Function[n, k = 0; m = n; While[m > 1, m = A007733[m]; k++]; k];
a = Function[n, t = 1; While[A256757[t] < n , t++]; t]; Table[a[n], {n, 0, 9}] (* Ivan Neretin, Apr 13 2015 *)

a007733(n) = znorder(Mod(2, n/2^valuation(n, 2)));
a256757(n) = {if (n==1, return(0)); nb = 1; while((n = a007733(n)) != 1, nb++); nb; }
a(n) = {k = 1; while(a256757(k) != n, k++); k;} \\ Michel Marcus, Apr 11 2015

a(15)-a(18) from Michel Marcus, Apr 11 2015

a(19)-a(21) from Amiram Eldar, Mar 04 2023

A007733 Period of binary representation of 1/n. Also, multiplicative order of 2 modulo the odd part of n (= A000265(n)).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, 6, 10, 11, 2, 20, 12, 18, 3, 28, 4, 5, 1, 10, 8, 12, 6, 36, 18, 12, 4, 20, 6, 14, 10, 12, 11, 23, 2, 21, 20, 8, 12, 52, 18, 20, 3, 18, 28, 58, 4, 60, 5, 6, 1, 12, 10, 66, 8, 22, 12, 35, 6, 9, 36, 20, 18, 30, 12, 39, 4, 54, 20, 82, 6

Offset: 1

N. J. A. Sloane, Hal Sampson (hals(AT)easynet.com)

Also sequence of period lengths for n's when you do primality testing and calculate "2^k mod n" from k = 0..n. - Gottfried Helms, Oct 05 2000
Fractal sequence related to A002326: the even terms of this sequence are this sequence itself, constructed on A002326, whose terms are the odd terms of this sequence. - Alexandre Wajnberg, Apr 27 2005
It seems that a(n) is also the sum of the terms in one period of the base-2 MR-expansion of 1/n (see A136042 for definition). - John W. Layman, Jan 22 2009
Indices n such that a(n) divides n are listed in A068563. - Max Alekseyev, Aug 25 2013
a(n) is the smallest k such that x^n - 1 factors into n linear polynomials over GF(2^k). For example, a(12) = 2, and x^12 - 1 = (x - 1)^4*(x - w)^4*(x - (w + 1))^4 in GF(4), where w^2 + w + 1 = 0. - Jianing Song, Jan 20 2019

Simmons, G. J. The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88, see Table 2. Math. Rev. 95f:05052.

Cf. A136042. - John W. Layman, Jan 22 2009
Cf. A000265, A002326, A256607, A256757.
Positions of records are A139099.

a007733 = a002326 . flip div 2 . subtract 1 . a000265
-- Reinhard Zumkeller, Apr 13 2015

f[n_] := MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]; Array[f, 84] (* Robert G. Wilson v, Jun 10 2011 *)

a(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ Michel Marcus, Apr 11 2015

from sympy.ntheory import n_order
def A007733(n): return n_order(2,n>>(~n & n-1).bit_length()) # Chai Wah Wu, Jul 01 2022

a(n) = A002326((A000265(n) - 1)/2). - Max Alekseyev, Jun 11 2009

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 1, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2

Offset: 1

Max Alekseyev, Oct 03 2013

a(n) >= A256757(n) - 1.

			a(18) = 2 because it takes two steps to reach 1 from 18: phi(18) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.
a(19) = 3 because it takes three steps to reach 1 from 19: phi(19) = 18, the odd part of which is 9, and phi(9) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.

T. D. Noe, Table of n, a(n) for n = 1..10000

A variant of A049115: a(n) = A049115(n) unless n is a power of 2.

Cf. A003434, A227946.

a227944 n = fst $
            until ((== 1) . snd) (\(i, x) -> (i + 1, a053575 x)) (0, n)
-- Reinhard Zumkeller, Oct 09 2013

oddPhi[n_] := Module[{phi = EulerPhi[n]}, phi/2^IntegerExponent[phi, 2]]; Table[Length[NestWhileList[oddPhi[#] &, n, # > 1 &]] - 1, {n, 100}] (* T. D. Noe, Oct 07 2013 *)

For n > 1, a(n) = a(A053575(n)) + 1.

A347386 Number of iterations of A347385 (Dedekind psi function applied to the odd part of n) needed to reach a power of 2.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 2, 2, 2, 1, 2, 1, 2, 0, 3, 2, 3, 2, 1, 2, 2, 1, 3, 2, 3, 1, 3, 2, 1, 0, 2, 3, 2, 2, 4, 3, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 4, 3, 3, 1, 3, 3, 3, 2, 2, 1, 2, 0, 2, 2, 4, 3, 2, 2, 3, 2, 5, 4, 3, 3, 2, 2, 3, 2, 4, 2, 2, 1, 4, 3, 3, 2, 4, 3, 2, 2, 1, 2, 3, 1, 3, 2, 3, 3, 4, 3, 3, 2, 2

Offset: 1

Antti Karttunen, Aug 31 2021

nonn

Also, for n > 1, one less than the number of iterations of A347385 to reach 1.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A000265, A001615, A209229, A347385, A347387 (the exponent of the eventual power of 2 reached).

Cf. also A003434, A019269, A227944, A256757, A331410, A336361 for similar sequences.

f[p_, e_] := If[p == 2, 1, (p + 1)*p^(e - 1)]; psiOdd[1] = 1; psiOdd[n_] := Times @@ f @@@ FactorInteger[n]; a[n_] := -1 + Length @ NestWhileList[psiOdd, n, # != 2^IntegerExponent[#, 2] &]; Array[a, 100] (* Amiram Eldar, Aug 31 2021 *)

A347385(n) = if(1==n,n, my(f=factor(n>>valuation(n, 2))); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1)));
A347386(n) = if(!bitand(n, n-1), 0, 1+A347386(A347385(n)));

If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A001615(A000265(n))).

For all n >= 1, a(n) <= A331410(n).

cp's OEIS Frontend

A256758 Position of first appearance of n in A256757.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A007733 Period of binary representation of 1/n. Also, multiplicative order of 2 modulo the odd part of n (= A000265(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A347386 Number of iterations of A347385 (Dedekind psi function applied to the odd part of n) needed to reach a power of 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula