A064097 -id:A064097 - cp's OEIS frontend

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 11, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 13, 11, 12, 12, 12, 12, 13, 11, 12, 12, 12, 13, 14, 12, 13, 13, 12, 12, 13, 13, 14, 13, 14, 13, 14, 12, 13, 13, 13, 13, 14, 13, 14

Offset: 1

N. J. A. Sloane

The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not ("pasting together" two 1's is not an allowed operation).
The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.
Guy asks if a(p) = a(p-1) + 1 for prime p. Martin Fuller found the least counterexample p = 353942783 in 2008, see Fuller link. - Charles R Greathouse IV, Oct 04 2012
It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - Gordon Hamilton and Brad Ballinger, May 23 2022
The second Altman links proves that {a(n) - 3*log_3(n)} is a well-ordered subset of the reals whose intersection with [0,k) has order type omega^k for each positive integer k, so this set itself has order type omega^omega. - Jianing Song, Apr 13 2024

			From _Lekraj Beedassy_, Jul 04 2009: (Start)
   n.........minimal expression........ a(n) = number of 1's
   1..................1...................1
   2.................1+1..................2
   3................1+1+1.................3
   4.............(1+1)*(1+1)..............4
   5............(1+1)*(1+1)+1.............5
   6............(1+1)*(1+1+1).............5
   7...........(1+1)*(1+1+1)+1............6
   8..........(1+1)*(1+1)*(1+1)...........6
   9...........(1+1+1)*(1+1+1)............6
  10..........(1+1+1)*(1+1+1)+1...........7
  11.........(1+1+1)*(1+1+1)+1+1..........8
  12.........(1+1)*(1+1)*(1+1+1)..........7
  13........(1+1)*(1+1)*(1+1+1)+1.........8
  14.......{(1+1)*(1+1+1)+1}*(1+1)........8
  15.......{(1+1)*(1+1)+1}*(1+1+1)........8
  16.......(1+1)*(1+1)*(1+1)*(1+1)........8
  17......(1+1)*(1+1)*(1+1)*(1+1)+1.......9
  18........(1+1)*(1+1+1)*(1+1+1).........8
  19.......(1+1)*(1+1+1)*(1+1+1)+1........9
  20......{(1+1+1)*(1+1+1)+1}*(1+1).......9
  21......{(1+1)*(1+1+1)+1}*(1+1+1).......9
  22.....{(1+1)*(1+1+1)+1}*(1+1+1)+1.....10
  23....{(1+1)*(1+1+1)+1}*(1+1+1)+1+1....11
  24......(1+1)*(1+1)*(1+1)*(1+1+1).......9
  25.....(1+1)*(1+1)*(1+1)*(1+1+1)+1.....10
  26....{(1+1)*(1+1)*(1+1+1)+1}*(1+1)....10
  27.......(1+1+1)*(1+1+1)*(1+1+1)........9
  28......(1+1+1)*(1+1+1)*(1+1+1)+1......10
  29.....(1+1+1)*(1+1+1)*(1+1+1)+1+1.....11
  30.....{(1+1+1)*(1+1+1)+1}*(1+1+1).....10
  31....{(1+1+1)*(1+1+1)+1}*(1+1+1)+1....11
  32....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)....10
  33...(1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1...11
  34..{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)..11
  .........................................
(End)

M. Criton, "Les uns de Germain", Problem No. 4, pp. 13 ; 68 in '7 x 7 Enigmes Et Défis Mathématiques pour tous', vol. 25, Editions POLE, Paris 2001.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.
K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (Dutch: On a maximum problem in arithmetic), Nieuw Arch. Wiskunde, (3) 1 (1953), pp. 1-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. F. Hasler, Table of n, a(n) for n = 1..10000
Harry Altman, Highest few sums and products of ones, Preprint, undated but before 2013.
Harry Altman, Integer Complexity and Well-Ordering, arXiv:1310.2894v1 [math.NT] , Oct 10, 2013.
Harry Altman and Joshua Zelinsky, Numbers with integer complexity close to the lower bound, arXiv:1207.4841 [math.NT], 2012.
J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.
J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]
J. Arias de Reyna, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.
J. Arias de Reyna and J. van de Lune, The question "How many 1's are needed?" revisited, arXiv preprint arXiv:1404.1850 [math.NT], 2014.
J. Arias de Reyna and J. van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183 [math.NT], 2014.
Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arxiv:1409.0446 [math.NT], 2014.
Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, On algorithms to calculate integer complexity, arXiv:1706.08424 [math.NT], 2017.
Martin N. Fuller, C program
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Qizheng He, Improved Algorithms for Integer Complexity, arXiv:2308.10301 [cs.DS], 2023.
Janis Iraids, Online calculator of a(n) for n < 10^12
Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer complexity: experimental and analytical results, arXiv:1203.6462 [math.NT], 2012.
Daniel A. Rawsthorne, How many 1's are needed?, Fibonacci Quarterly 27 (1989), pp. 14-17.
Srinivas, Vivek V. and Shankar, B. R., Integer Complexity: Breaking the Theta(n^2) barrier, World Academy of Science 41 (2008), pp. 690-691.
Stefan Steinerberger, A Short Note on Integer Complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014).
Stefan Steinerberger, A short note on integer complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014). [Cached copy, with permission.]
Joshua Zelinsky, Upper Bounds on Integer Complexity, arXiv preprint (2022). arXiv:2211.02995 [math.NT]
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, YouTube video, 2012.
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, Journal of Number Theory, Volume 133, Issue 2, February 2013, Pages 391-397.
Eric Weisstein's World of Mathematics, Integer Complexity
Dimitri Zucker, The Most Underrated Concept in Number Theory, Combo Class Youtube video that mentions this sequence.
Index to sequences related to the complexity of n

Cf. A025280 (variant using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348089 (using +, -, *, / and ^), A348262 (using + and ^).

Cf. A000792 (largest integer of given complexity), A003313, A076142, A076091, A061373, A005421, A064097, A005520, A003037, A161906, A161908, A244743.

import Data.List (genericIndex)
a005245 n = a005245_list `genericIndex` (n-1)
a005245_list = 1 : f 2 [1] where
   f x ys = y : f (x + 1) (y : ys) where
     y = minimum $
         (zipWith (+) (take (x `div` 2) ys) (reverse ys)) ++
         (zipWith (+) (map a005245 $ tail $ a161906_row x)
                      (map a005245 $ reverse $ init $ a161908_row x))
-- Reinhard Zumkeller, Mar 08 2013

with(numtheory):
a:= proc(n) option remember;
      `if`(n=1, 1, min(seq(a(i)+a(n-i), i=1..n/2),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Apr 18 2012

a[n_] := a[n] = If[n == 1, 1,
   Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~
   Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)

A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);
if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */,
A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);
for(i=1, n-1, A005245[i] || A005245[i]=A005245(i,lim)); /* compute all previous elements */
A005245[n]=min( vecmin(vector(min(n\2,if(lim>0,lim,n)), k, A005245[k]+A005245[n-k])) /* additive possibilities - if lim>0 is given, consider a(k)+a(n-k) only for k<=lim - we know it is save to use lim=1 up to n=2e7 */, if( isprime(n), n, vecmin(vector((-1+#d=divisors(n))\2, i, A005245[d[i+1]]+A005245[d[ #d-i]]))/* multiplicative possibilities */))}
\\ See also the Python program by Tim Peters at A005421.
\\ M. F. Hasler, Jan 30 2008

from functools import lru_cache
from itertools import takewhile
from sympy import divisors
@lru_cache(maxsize=None)
def A005245(n): return min(min(A005245(a)+A005245(n-a) for a in range(1,(n>>1)+1)),min((A005245(d)+A005245(n//d) for d in takewhile(lambda d:d*d<=n,divisors(n)) if d>1),default=n)) if n>1 else 1 # Chai Wah Wu, Apr 29 2023

It is known that a(n) <= A061373(n) but I think 0 <= A061373(n) - a(n) <= 1 also holds. - Benoit Cloitre, Nov 23 2003 [That's false: the numbers {46, 235, 649, 1081, 7849, 31669, 61993} require {1, 2, 3, 4, 5, 6, 7} fewer 1's in A005245 than in A061373. - Ed Pegg Jr, Apr 13 2004]
It is known from the work of Selfridge and Coppersmith that 3 log_3 n <= a(n) <= 3 log_2 n = 4.754... log_3 n for all n > 1. [Guy, Unsolved Problems in Number Theory, Sect. F26.] - Charles R Greathouse IV, Apr 19 2012 [Comment revised by N. J. A. Sloane, Jul 17 2016]
Zelinsky (2022) improves the upper bound to a(n) <= A*log n where A = 41/log(55296) = 3.754422.... This compares to the constant 2.7307176... of the lower bound. - Charles R Greathouse IV, Dec 11 2022
a(n) >= A007600(n) is a very accurate lower bound. - Mehmet Sarraç, Dec 18 2022

More terms from David W. Wilson, May 15 1997

A067513 Number of divisors d of n such that d+1 is prime.

Original entry on oeis.org

1, 2, 1, 3, 1, 3, 1, 3, 1, 3, 1, 5, 1, 2, 1, 4, 1, 4, 1, 4, 1, 3, 1, 5, 1, 2, 1, 4, 1, 5, 1, 4, 1, 2, 1, 7, 1, 2, 1, 5, 1, 4, 1, 4, 1, 3, 1, 6, 1, 3, 1, 4, 1, 4, 1, 4, 1, 3, 1, 8, 1, 2, 1, 4, 1, 5, 1, 3, 1, 4, 1, 8, 1, 2, 1, 3, 1, 4, 1, 6, 1, 3, 1, 7, 1, 2, 1, 5, 1, 6, 1, 4, 1, 2, 1, 7, 1, 2, 1, 5, 1, 4, 1

Offset: 1

Amarnath Murthy, Feb 12 2002

1, 2 and 4 are the only numbers such that for every divisor d, d+1 is a prime.
These and only these primes appear as prime divisors of any term of InvPhi(n) set if n is not empty, i.e., if n is from A002202. - Labos Elemer, Jun 24 2002
a(n) is the number of integers k such that n = k - k/p where p is one of the prime divisors of k. (See, e.g., A064097 and A333123, which are related to the mapping k -> k - k/p.) - Robert G. Wilson v, Jun 12 2022

			a(12) = 5 as the divisors of 12 are 1, 2, 3, 4, 6 and 12 and the corresponding primes are 2,3,5,7 and 13. Only 3+1 = 4 is not a prime.

T. D. Noe, Table of n, a(n) for n = 1..10000
Yuchen Ding, On a conjecture of R. M. Murty and V. K. Murty, arXiv:2208.06704 [math.NT], 2022.
Yuchen Ding, On a conjecture of R. M. Murty and V. K. Murty II, arXiv:2209.01087 [math.NT], 2022-2023.
Steve Fan and Carl Pomerance, Shifted-prime divisors, arXiv:2401.10427 [math.NT], 2024.
Mikhail R. Gabdullin, Moments of the shifted prime divisor function, arXiv preprint (2025). arXiv:2505.24050 [math.NT]
M. Ram Murty and V. Kumar Murty, A variant of the Hardy-Ramanujan theorem, Hardy-Ramanujan Journal, Vol. 44 (2021), pp. 32-40.
Karl Prachar, Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form p-1 haben, Monatshefte für Mathematik, Vol. 59 (1955), pp. 91-97.

Even-indexed terms give A046886.
Cf. A000005, A001221, A001222, A002202, A027750, A064097, A141197, A185633, A202727, A202728, A322312, A322976, A333123, A346467, A355452.
Cf. A005408 (positions of 1's), A051222 (of 2's).

a067513 = sum . map (a010051 . (+ 1)) . a027750_row
-- Reinhard Zumkeller, Jul 31 2012

A067513 := proc(n)
    local a,d;
    a := 0 ;
    for d in numtheory[divisors](n) do
        if isprime(d+1) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A067513(n),n=1..100) ; # R. J. Mathar, Aug 07 2022

a[n_] := Length[Select[Divisors[n]+1, PrimeQ]]
Table[Count[Divisors[n],?(PrimeQ[#+1]&)],{n,110}] (* _Harvey P. Dale, Feb 29 2012 *)
a[n_] := DivisorSum[n, 1 &, PrimeQ[# + 1] &]; Array[a, 100] (* Amiram Eldar, Jan 11 2025 *)

a(n)=sumdiv(n,d,isprime(d+1)) \\ Charles R Greathouse IV, Dec 23 2011

from sympy import divisors, isprime
def a(n): return sum(1 for d in divisors(n, generator=True) if isprime(d+1))
print([a(n) for n in range(1, 104)]) # Michael S. Branicky, Jul 12 2022

a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - Vladeta Jovovic, Feb 13 2002
a(n) <= A141197(n). - Reinhard Zumkeller, Oct 06 2008
a(n) = A001221(A027760(n)). - Enrique Pérez Herrero, Dec 23 2011
a(n) = Sum_{k = 1..A000005(n)} A010051(A027750(n,k)+1). - Reinhard Zumkeller, Jul 31 2012
a(n) = A001221(A185633(n)) = A001222(A322312(n)). - Antti Karttunen, Jul 12 2022
Sum_{k=1..n} a(k) = n * (log(log(n)) + B) + O(n/log(n)), where B is a constant (Prachar, 1955). - Amiram Eldar, Jan 11 2025

Edited by Dean Hickerson, Feb 12 2002

A333123 Consider the mapping k -> (k - (k/p)), where p is any of k's prime factors. a(n) is the number of different possible paths from n to 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3, 3, 5, 5, 1, 1, 5, 5, 3, 10, 5, 5, 4, 3, 7, 5, 9, 9, 12, 12, 1, 17, 2, 21, 9, 9, 14, 16, 4, 4, 28, 28, 9, 21, 14, 14, 5, 28, 7, 7, 12, 12, 14, 16, 14, 28, 23, 23, 21, 21, 33, 42, 1, 33, 47, 47, 3, 61, 56, 56, 14, 14, 23, 28, 28, 103, 42, 42, 5

Offset: 1

Ali Sada and Robert G. Wilson v, Mar 09 2020

The iteration always terminates at 1, regardless of the prime factor chosen at each step.
Although there may exist multiple paths to 1, their path lengths (A064097) are the same! See A064097 for a proof. Note that this behavior does not hold if we allow any divisor of k.
First occurrence of k or 0 if no such value exists: 1, 6, 12, 24, 14, 96, 26, 85, 28, 21, 578, 30, 194, 38, 164, 39, 33, 104, 1538, 112, 35, 328, 58, 166, ..., .
Records: 1, 2, 3, 5, 10, 12, 17, 21, 28, 33, 42, 47, 61, 103, 168, ..., .
Record indices: 1, 6, 12, 14, 21, 30, 33, 35, 42, 62, 63, 66, 69, ..., .
When viewed as a graded poset, the paths of the said graph are the chains of the corresponding poset. This poset is also a lattice (see Ewan Delanoy's answer to Peter Kagey's question at the Mathematics Stack Exchange link). - Antti Karttunen, May 09 2020

			a(1): {1}, therefore a(1) = 1;
a(6): {6, 4, 2, 1} or {6, 3, 2, 1}, therefore a(6) = 2;
a(12): {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, therefore a(12) = 3;
a(14): {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, therefore a(14) = 5.
From _Antti Karttunen_, Apr 05 2020: (Start)
For n=15 we have five alternative paths from 15 to 1: {15, 10, 5, 4, 2, 1}, {15, 10, 8, 4, 2, 1}, {15, 12, 8, 4, 2, 1},  {15, 12, 6, 4, 2, 1},  {15, 12, 6, 3, 2, 1}, therefore a(15) = 5. These form a graph illustrated below:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \_   |  __/|
     \__|_/   |
        4     3
         \   /
          \ /
           2
           |
           1
(End)

Antti Karttunen, Table of n, a(n) for n = 1..20000
Peter Kagey, Mathematics Stack Exchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?

Cf. A064097, A332809 (size of the lattice), A332810.
Cf. A332904 (sum of distinct integers present in such a graph/lattice), A333000 (sum over all paths), A333001, A333785.
Cf. A332992 (max. outdegree), A332999 (max. indegree), A334144 (max. rank level).
Cf. A334230, A334231 (meet and join).
Partial sums of A332903.
Cf. also tables A334111, A334184.

a[n_] := Sum[a[n - n/p], {p, First@# & /@ FactorInteger@n}]; a[1] = 1; (* after PARI coding by Rémy Sigrist *) Array[a, 70]
(* view the various paths *)
f[n_] := Block[{i, j, k, p, q, mtx = {{n}}}, Label[start]; If[mtx[[1, -1]] != 1, j = Length@ mtx;  While[j > 0, k = mtx[[j, -1]]; p = First@# & /@ FactorInteger@k; q = k - k/# & /@ p; pl = Length@p; If[pl > 1, Do[mtx = Insert[mtx, mtx[[j]], j], {pl - 1}]]; i = 1;  While[i < 1 + pl, mtx[[j + i - 1]] = Join[mtx[[j + i - 1]], {q[[i]]}]; i++]; j--]; Goto[start], mtx]]

for (n=1, #a=vector(80), print1 (a[n]=if (n==1, 1, vecsum(apply(p -> a[n-n/p], factor(n)[,1]~)))", ")) \\ Rémy Sigrist, Mar 11 2020

a(n) = 1 iff n is a power of two (A000079) or a Fermat Prime (A019434).
a(p) = a(p-1) if p is prime.
a(n) = Sum_{p prime and dividing n} a(n - n/p) for any n > 1. - Rémy Sigrist, Mar 11 2020

A064415 a(1) = 0, a(n) = iter(n) if n is even, a(n) = iter(n)-1 if n is odd, where iter(n) = A003434(n) = smallest number of iterations of Euler totient function phi needed to reach 1.

Original entry on oeis.org

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

Offset: 1

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001

nonn

a(n) is the exponent of the eventual power of 2 reached when starting from k=n and then iterating the nondeterministic map k -> k-(k/p), where p can be any odd prime factor of k, for example, the largest. Note that each original odd prime factor p of n brings its own share of 2's to the final result after it has been completely processed (with all intermediate odd primes also eliminated, leaving only 2's). As no 2's are removed, also all 2's already present in the original n are included in the eventual power of 2 that is reached, implying that a(n) >= A007814(n). - Antti Karttunen, May 13 2020

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

Cf. A000010, A003434, A007814, A052126, A054725, A064097, A064416, A064674, A171462, A291783, A329697.
The 2-adic valuation of A309243.
Partial sums of A334195. Cf. A053044 for partial sums of this sequence.
Cf. also A334097 (analogous sequence when using the map k -> k + k/p).

a064415 1 = 0
a064415 n = a003434 n - n `mod` 2 -- Reinhard Zumkeller, Sep 18 2011

A003434(n)=for(k=0, n, n>1 || return(k); n=eulerphi(n));
a(n) = if( n<=2, n-1, A003434(n) - (n%2) );
vector(200, n, a(n)) \\ Joerg Arndt, Apr 08 2014

A064415(n) = if(!bitand(n,n-1),valuation(n,2),A064415(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, May 13 2020

A064415(n) = if(1==n, 0, if(isprime(n), 1+A064415(n>>1), my(f=factor(n)); (apply(A064415, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, May 13 2020

For all integers m >0 and n>0 a(m*n)=a(m)+a(n). The function a(n) is completely additive. The smallest integer q which satisfy the equation a(q)=n is 2^q, the greatest is 3^q. For all integers n>0, the counter image off n, a^-1(n) is finite.
a(1) = 0 and a(n) = A054725(n) for n>=2. - Joerg Arndt, Apr 08 2014, A-number corrected by Antti Karttunen, May 13 2020
From Antti Karttunen, May 13 2020: (Start)
For n > 1, a(n) = A003434(n) - A000035(n).
a(1) = 0, a(2) = 1 and for n > 2, a(n) = sum(p | n, a(p-1)), where sum is over all primes p that divide n, with multiplicity. (Cf. A054725).
a(1) = 0, a(2) = 1 and a(p) = 1 + a((p-1)/2) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [From above formula, 1+ compensates for the "lost" 2]
a(n) = A007814(A309243(n)). [From Rémy Sigrist's conjecture in the latter sequence. This reduces to a(n) = sum(p|n, a(p-1)) formula above, thus holds also]
If A209229(n) = 1 [when n is a power of 2], a(n) = A007814(n), otherwise a(n) = a(n-A052126(n)) = a(A171462(n)). [From the definition in the comments]
a(n) = A064097(n) - A329697(n).
a(2^k) = a(3^k) = k.
(End)

More terms from David Wasserman, Jul 22 2002

Definition corrected by Reinhard Zumkeller, Sep 18 2011

A332809 Number of distinct integers encountered on possible paths from n to 1 when iterating the nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Original entry on oeis.org

1, 2, 3, 3, 4, 5, 6, 4, 6, 6, 7, 7, 8, 9, 10, 5, 6, 9, 10, 8, 12, 10, 11, 9, 9, 11, 10, 12, 13, 14, 15, 6, 17, 8, 18, 12, 13, 14, 15, 10, 11, 17, 18, 13, 18, 15, 16, 11, 18, 12, 14, 14, 15, 14, 16, 15, 17, 17, 18, 18, 19, 20, 20, 7, 22, 23, 24, 10, 26, 24, 25, 15, 16, 17, 21, 18, 30, 20, 21, 12, 15, 14, 15, 22, 16, 24, 25, 16

Offset: 1

Antti Karttunen, Apr 04 2020

The count includes also n itself, and the final 1 when it is distinct from n.

a(n) >= A000005(n) because all divisors of n can be found in the union of those paths. - Antti Karttunen, Apr 19 2020

			a(1): {1}, therefore a(1) = 1;
a(6): we have two alternative paths: {6, 4, 2, 1} or {6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6] present, therefore a(6) = 5;
a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 7;
a(14): we have five alternative paths: {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 7, 8, 12, 14] present in at least one of the paths, therefore a(14) = 9.

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

Cf. A064097, A332810, A333123, A334230, A334231, A333786 (first occurrence of each n), A334112.
Partial sums of A332902.
See A332904 for the sum.

a[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[ lst, {Union[ Flatten[# - #/(First@# & /@ FactorInteger@#) & /@ lst[[-1]]]]}]]; Length@ Union@ Flatten@ lst]; Array[a, 75] (* Robert G. Wilson v, Apr 06 2020 *)

up_to = 105;
A332809list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2,up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1,#f,s = setunion(s,v[n-(n/f[i])])); v[n] = s); apply(length,v); }
v332809 = A332809list(up_to);
A332809(n) = v332809[n];

from sympy import factorint
from functools import cache
@cache
def b(n): return {n}.union(*(b(n - n//p) for p in factorint(n)))
def a(n): return len(b(n))
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Aug 13 2022

a(p) = 1 + a(p-1) for all primes p.
a(n) = n - A332810(n).
a(n) = A334112(n) + A000005(n). - Antti Karttunen, May 09 2020

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 10, 8, 15, 13, 16, 12, 22, 14, 22, 21, 31, 18, 31, 20, 36, 29, 34, 24, 46, 31, 40, 40, 50, 30, 51, 32, 63, 45, 52, 43, 67, 38, 58, 53, 76, 42, 71, 44, 78, 66, 70, 48, 94, 57, 81, 69, 92, 54, 94, 67, 106, 77, 88, 60, 111, 62, 94, 92, 127, 79, 111, 68, 120, 93, 113, 72, 139, 74, 112, 106, 134, 89, 131, 80, 156, 121

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

Sum of those divisors of n that can be obtained by repeatedly taking the largest proper divisor (of previous such divisor, starting from n, which is included in the sum), up to and including the terminal 1.

			a(18) = 18 + 18/2 + 9/3 + 3/3 = 18 + 9 + 3 + 1 = 31.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000203, A006022, A032742, A064097, A073934, A332994, A333783, A333791, A333794.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));

a(1) = 1; and for n > 1, a(n) = n + a(A032742(n)).
a(n) = n + A006022(n).
a(n) = A332994(n) + A333791(n).
a(n) = A000203(n) - A333783(n).
It seems that for all n >= 1, a(n) <= A073934(n) <= A333794(n).

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Original entry on oeis.org

2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692

Offset: 1

Ali Dasdan, Apr 05 2012

			a(2) = 2 because two 2's can produce 0 = 2-2, 1 = 2/2, 4 = 2+2 = 2*2, so the smallest positive integer that cannot be computed is 2.
a(3) = 1 because no expression with three 3's gives 1.

Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.

Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.

f:= proc(n,b) option remember;
      `if`(n=1, {b}, {seq(seq(seq([k+m, k-m, k*m,
      `if`(m=0, NULL, k/m)][], m=f(n-i, b)), k=f(i, b)), i=1..n-1)})
    end:
a:= proc(n) local i, l;
      l:= sort([infinity, select(x-> is(x, integer) and x>0, f(n, n))[]]);
      for i do if l[i]<>i then return i fi od
    end:
seq(a(n), n=1..8); # Alois P. Heinz, Apr 13 2012

from fractions import Fraction
from functools import lru_cache
def a(n):
    @lru_cache()
    def f(m):
        if m == 1: return {Fraction(n, 1)}
        out = set()
        for j in range(1, m//2+1):
            for x in f(j):
                for y in f(m-j):
                    out.update([x + y, x - y, y - x, x * y])
                    if y: out.add(Fraction(x, y))
                    if x: out.add(Fraction(y, x))
        return out
    k, s = 1, f(n)
    while k in s: k += 1
    return k
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jul 29 2022

a(11)-a(12) from Alois P. Heinz, Apr 22 2012
a(13)-a(14) from Michael S. Branicky, Jul 29 2022
a(15) from Michael S. Branicky, Jul 27 2023

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jul 22 2020

nonn

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

Cf. A000010, A000265, A003434, A005087, A046660, A064097, A064415, A329697, A336396, A336477.

Cf. A003401 (positions of zeros).

Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A336469(n) = A329697(eulerphi(n));
\\ Or alternatively as:
A336469(n) = { my(f = factor(n)); sum(k=1, #f~, if(2==f[k,1],0,-1 + (f[k, 2]*A329697(f[k, 1])))); };

Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e*A329697(p) - 1.

a(n) = A329697(n) - A005087(n) = A336396(n) + A046660(A000265(n)).

A073933 Number of terms in n-th row of triangle in A073932.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 6, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 9, 8, 8, 9, 10, 7, 9, 8, 8, 8, 9, 8, 9, 8, 9, 9, 10, 8, 9, 9, 9, 7, 9, 9, 10, 8, 10, 9, 10, 8, 9, 9, 9, 9, 10, 9, 10, 8, 9, 9, 10, 9, 9, 10, 10, 9, 10, 9, 10, 10, 10, 11, 10, 8

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

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

Cf. A032742, A060681, A073932, A073934, A073935.

One more than A064097.

a[1] := 1:for i from 2 to 500 do n := i:s := 1:while(n>1) do if isprime(n) then r := n-1: else r := n-n/ifactors(n)[2][1][1]; fi; n := r:s := s+1:od:a[i] := s:od:seq(a[k],k=1..500);

(define (A073933 n) (if (= 1 n) n (+ 1 (A073933 (A060681 n)))))
(define (A060681 n) (- n (A032742 n))) ;; See also code under A032742
;; Antti Karttunen, Aug 23 2017

From Antti Karttunen, Aug 23 2017: (Start)
a(1) = 1; for n > 1, a(n) = 1 + a(A060681(n)).
a(n) = 1 + A064097(n).
(End)

More terms from Sascha Kurz, Aug 23 2002

Offset corrected from 0 to 1 by Antti Karttunen, Aug 23 2017

A323077 Number of iterations of map x -> (x - (largest divisor d < x)) needed to reach 1 or a prime, when starting at x = n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 04 2019

nonn

When iteration is started from n, the first noncomposite reached is A006530(n), from which follows the new formula a(n) = A064097(A052126(n)) = A064097(n/A006530(n)), as A064097 is completely additive sequence. - Antti Karttunen, May 15 2020

Antti Karttunen, Table of n, a(n) for n = 1..12005
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A006530, A032742, A052126, A060681, A064097, A323076, A334202, A334203.
Cf. A334198 (positions of the records, also the first occurrence of each n).
Differs from A334201 for the first time at n=169, where a(169) = 5, while A334201(169) = 6.

Nest[Append[#1, If[PrimeOmega[#2] <= 1, 0, 1 + #1[[Max@ Differences@ Divisors[#2] ]] ]] & @@ {#, Length@ # + 1} &, {}, 105] (* Michael De Vlieger, May 26 2020 *)

A060681(n) = (n-if(1==n,n,n/vecmin(factor(n)[,1])));
A323077(n) = if(1>=bigomega(n),0,1+A323077(A060681(n)));

If A001222(n) <= 1 [when n is 1 or a prime], a(n) = 0, otherwise a(n) = 1 + a(A060681(n)).
a(n) <= A064097(n).
a(n) = A064097(n) - A334202(n) = A064097(A052126(n)). - Antti Karttunen, May 13 2020
a(A334198(n)) = n for all n >= 0. - Antti Karttunen, May 19 2020

cp's OEIS Frontend

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A067513 Number of divisors d of n such that d+1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A333123 Consider the mapping k -> (k - (k/p)), where p is any of k's prime factors. a(n) is the number of different possible paths from n to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A064415 a(1) = 0, a(n) = iter(n) if n is even, a(n) = iter(n)-1 if n is odd, where iter(n) = A003434(n) = smallest number of iterations of Euler totient function phi needed to reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

PARI

PARI

Formula

Extensions

A332809 Number of distinct integers encountered on possible paths from n to 1 when iterating the nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Views

Author

Keywords

Comments

Examples

Links