A000196 -id:A000196 - cp's OEIS frontend

A334870 If n is a square, a(n) = A000196(n), and for nonsquare n, let p be the smallest prime dividing the squarefree part of n. Divide n by p and multiply by the product of all smaller primes.

1, 1, 2, 2, 6, 3, 30, 4, 3, 5, 210, 8, 2310, 7, 10, 4, 30030, 9, 510510, 24, 14, 11, 9699690, 12, 5, 13, 18, 120, 223092870, 15, 6469693230, 16, 22, 17, 42, 6, 200560490130, 19, 26, 20, 7420738134810, 21, 304250263527210, 840, 54, 23, 13082761331670030, 32, 7, 25, 34, 9240, 614889782588491410, 27, 66, 28, 38, 29

Offset: 1

Antti Karttunen, Jun 08 2020

nonn

Each natural numbers occurs exactly twice in this sequence.
In binary trees like A334860 and A334866, for n > 2, a(n) gives the parent node of node n.
For nonsquare numbers, n, with squarefree part A019565(k) and square part m, a(n) is the number with squarefree part A019565(k-1) and square part m. - Peter Munn, Jul 14 2020

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

A left inverse of A334747.

Cf. A000196, A019565, A225546, A252463, A334860, A334866, A334868, A334869, A334871, A334872.

Array[If[IntegerQ[#2], #2, #1/#2*Product[Prime@i, {i, PrimePi@#2 - 1}] & @@ {#1, FactorInteger[#2 /. (c_ : 1)*a_^(b_ : 0) :> (c*a^b)^2][[1, 1]]}] & @@ {#, Sqrt[#]} &, 58] (* Michael De Vlieger, Jun 26 2020 *)

A334870(n) = if(issquare(n),sqrtint(n),my(c=core(n), m=n); forprime(p=2, , if(!(c % p), m/=p; break, m*=p)); (m));

a(A334747(n)) = n.
a(A000040(n)) = A002110(n-1).
a(n^2) = n.
a(n) = A225546(A252463(A225546(n))). - Peter Munn, Jun 08 2020

A079051 Recamán variation: a(0) = 0; for n >= 1, a(n) = a(n-1) - f(n) if that number is positive and not already in the sequence, otherwise a(n) = a(n-1) + f(n), where f(n) = floor(sqrt(n)) (A000196).

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 9, 11, 13, 10, 13, 16, 19, 22, 25, 28, 24, 20, 24, 28, 32, 36, 40, 44, 48, 43, 38, 33, 38, 43, 48, 53, 58, 63, 68, 73, 67, 61, 55, 49, 55, 61, 67, 73, 79, 85, 91, 97, 103, 96, 89, 82, 75, 82, 89, 96, 103, 110, 117, 124, 131, 138, 145, 152, 144, 136, 128, 120

Offset: 0

Benoit Cloitre, Feb 02 2003

nonn

N. J. A. Sloane and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.

Ivan Neretin, Table of n, a(n) for n = 0..10000
Nick Hobson, Python program for this sequence

Cf. A000196, A005132. Numbers missed are in A117247.

Cf. A117248, A117516, A117518.

Fold[Append[#1, If[MemberQ[#1, (a = #1[[-1]]) - (r = Floor@Sqrt@#2)], a + r, a - r]] &, {0, 1}, Range[2, 70]] (* Ivan Neretin, Apr 22 2018 *)

lista(nn) = {va = vector(nn+1); last = 0; for (n=1, nn, new = last - sqrtint(n); if ((new <= 0) || vecsearch(vecsort(va,,8), new), new = last + sqrtint(n)); va[n+1] = new; last = new;); va;} \\ Michel Marcus, Apr 23 2018

Conjecture: for n>100, 1/2 < a(n)/(n*log(n)) < 1.

The conjecture is false. In fact, a(n) = n^(3/2)/6 + O(n). - N. J. A. Sloane, Apr 29 2006

A262689 a(n) = largest number k <= A000196(n) for which A002828(n-(k^2)) = A002828(n)-1.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 03 2015

nonn

a(n) = square root of the largest summand present among all representations of n as a minimal number of squares, A002828(n). See the last two examples.

			For n = 9, we have A002828(9) = 1 because 9 is itself a perfect square. By the definition of this sequence, we find the largest k <= 3 for which A002828(9 - k^2) = A002828(9)-1 = 0, and it is k=3 that satisfies this condition, thus a(9) = 3.
For n = 27, by the other interpretation given in the Comments section, we see that the two minimal sums requiring the least number of squares (= 3 = A002828(27)) are (25 + 1 + 1) and (9 + 9 + 9). As 25 is larger than 9, we have a(27) = sqrt(25) = 5.
For n = 33, the two minimal solutions are (25 + 4 + 4) and (16 + 16 + 1). As 25 is larger than 16, we have a(33) = sqrt(25) = 5.

Antti Karttunen, Table of n, a(n) for n = 0..65536

Cf. A000196, A002828, A010052, A064876, A180466, A262690.

Differs from A064876 for the first time at n=33, where a(33) = 5, while A064876(33) = 4.

Other identities. For all n >= 0:
a(n) = A000196(A262690(n)).
a(n^2) = n.

A139004 Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 4.

Original entry on oeis.org

2, 1, 10, 0, 7, 11, 24, 27, 29, 9, 36, 40, 36, 17, 37, 31, 22, 31, 37, 42, 19, 37, 21, 1, 26, 13, 51, 41, 36, 6, 30, 41, 44, 33, 16, 33, 31, 64, 35, 50, 25, 43, 12, 18, 41, 18, 42, 55, 39, 23, 71, 65, 45, 43, 52, 39, 49, 44, 51, 60, 57, 59, 24, 66, 26, 36, 46, 51, 46, 26, 48, 76

Offset: 1

M. F. Hasler, Apr 09 2008

nonn

Knuth conjectured that any number can be obtained in this way, starting from 4.
This sequence gives the minimal number of operations needed to do so.
To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.
If we are allowed to use tan(x) just once, then a single 2 is enough to get any positive integer, if Knuth's conjecture that one 4 is enough is true. From 2, (((-tan(2.))!)!)! = 5.592..., then floor, factorial gets 120, then sqrt, sqrt gives 3.162..., and floor gives 3, or negate, floor, negate gives 4. - N. J. A. Sloane, Feb 26 2025
The article by Bendersky is relevant because it gives an explicit formula for n using four 2's (and some logs). Good illustration of techniques. - N. J. A. Sloane, Feb 26 2025

			Representing the operation x -> floor(sqrt(x)) by "s" and x -> x! by "f", we have:
a(1) = 2 since 1 = ss4 is clearly the shortest way to obtain 1, starting with 4.
a(2) = 1 since 2 = s4 is clearly the shortest way to obtain 2, starting with 4.
a(4) = 0 since no operation is required to get 4.
a(3) = 10 = 3+a(5) since 3 = ssf5 and it cannot be obtained from 4 with fewer operations.
a(5) = 7 since 5 = sssssff4.
a(6) = 11 = 1+a(3) since 6 = f3. a(10) = 9 since 10 = sfsssssff4 is the shortest way to obtain 9, starting with 4.

Jon E. Schoenfield, Table of n, a(n) for n = 1..1000
Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025
Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025 [Local copy, with the author's permission]
D. E. Knuth, Representing numbers using only one 4, Mathematics Magazine, Vol. 37, No. 5 (Nov. 1964), pp. 308-310.
John E. Maxfield, A Note on N!, Mathematics Magazine, Vol. 43, No. 2 (March 1970), pp. 64-67.
Perlmonks.org, Chasing Knuth's Conjecture.
Jon E. Schoenfield, Table of n, a(n), and shortest path for n = 1..1000

Cf. A139003, A055226.

A139004( n, S=Set(4), LIM=10^4 )={ for( i=0,LIM, setsearch( S, n) & return(i); S=setunion( S, setunion( Set( vector( #S, j, sqrtint(eval(S[j])))), Set( vector( #S, j, if( LIM > j=eval(S[j]), j!))))))}

{ search(x,r,l=0) = local(ll,xx); ll=l; xx=x; while(llMax Alekseyev, Nov 01 2008

a(4) = 0, a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }

a(7)-a(9) from Max Alekseyev, Oct 17, Nov 01 2008

More terms from Jon E. Schoenfield, Nov 10 2008

A157942 Numbers n divisible by the largest prime <= sqrt(n), A007917(A000196(n)).

Original entry on oeis.org

4, 6, 8, 9, 12, 15, 18, 21, 24, 25, 30, 35, 40, 45, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 121, 132, 143, 154, 165, 169, 182, 195, 208, 221, 234, 247, 260, 273, 286, 289, 306, 323, 340, 357, 361, 380, 399, 418, 437, 456, 475, 494, 513, 529, 552, 575, 598

Offset: 1

M. F. Hasler, Mar 09 2009

nonn

Includes squares of primes (A001248; exactly the cases where we have "=" in the definition) and products of pairs of consecutive primes (A006094) as subsequences.

Select[Range[4,599],IntegerQ[#/Prime[PrimePi[Sqrt[#]]]]&] (* Jayanta Basu, May 03 2013 *)

for( n=4,999, n % precprime(sqrtint(n)) || print1(n","))

A237273 Triangle read by rows: T(n,k) = k+m, if k < m and k*m = n, or T(n,k) = k, if k^2 = n. Otherwise T(n,k) = 0. With n>=1 and 1<=k<=A000196(n).

Original entry on oeis.org

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

Offset: 1

Omar E. Pol, Feb 08 2014

The first element of column k is in row k^2.
Column k lists k, k-1 zeros, and the positive integers but starting from 2*k+1 interleaved with k-1 zeros.
Row n has only one positive term iff n is a noncomposite number (A008578).
It appears that there are only eight rows that do not contain zeros. The indices of these rows are in A018253 (the divisors of 24).

			Triangle begins:
1;
3;
4;
5,   2;
6,   0;
7,   5;
8,   0;
9,   6;
10,  0,  3;
11,  7,  0;
12,  0,  0;
13,  8,  7;
14,  0,  0;
15,  9,  0;
16,  0,  8;
17, 10,  0,  4;
18,  0,  0,  0;
19, 11,  9,  0;
20,  0,  0,  0;
21, 12,  0,  9;
22,  0, 10,  0;
23, 13,  0,  0;
24,  0,  0,  0;
25, 14, 11, 10;
26,  0,  0,  0,   5;
27, 15,  0,  0,   0;
28,  0, 12,  0,   0;
29, 16,  0, 11,   0;
30,  0,  0,  0,   0;
31, 17, 13,  0,  11;
...
For n = 9 the divisors of n are 1, 3, 9, so row 9 is 10, 0, 3, because 1*9 = 9 and 3^2 = 9. The sum of row 9 is A000203(9) = 13.
For n = 12 the divisors of 12 are 1, 2, 3, 4, 6, 12, so row 12 is 13, 8, 7, because 1*12 = 12, 2*6 = 12 and 3*4 = 12. The sum of row 12 is A000203(12) = 28.

Index entries for sequences related to sigma(n)

Row sums give A000203.
Row n has length A000196(n).
Column 1 is A065475.
Cf. A000290, A008578, A018253, A027750, A196020, A210959, A212119, A212120, A228812-A228814, A231347, A236104, A236631, A237519, A237593.

T(n, k) = if (n % k, 0, if (k^2==n, k, k + n/k));
tabf(nn) = {for (n = 1, nn, v = vector(sqrtint(n), k, T(n, k)); print(v););} \\ Michel Marcus, Jun 19 2019

A157941 Numbers n divisible by the largest prime < sqrt(n), A007917(A000196(n-1)).

Original entry on oeis.org

6, 8, 12, 15, 18, 21, 24, 30, 35, 40, 45, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 132, 143, 154, 165, 182, 195, 208, 221, 234, 247, 260, 273, 286, 306, 323, 340, 357, 380, 399, 418, 437, 456, 475, 494, 513, 552, 575, 598, 621, 644, 667, 690, 713, 736, 759

Offset: 1

M. F. Hasler, Mar 09 2009

nonn

Includes products of pairs of consecutive primes (A006094) as subsequence, equals A157942 with squares of primes (A001248) removed.

For a number < 5 the definition does not make much sense, since there is no prime < sqrt(4) = 2, so we don't consider them here.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Select[Range[6,800],Divisible[#,NextPrime[Sqrt[#],-1]]&] (* Harvey P. Dale, Sep 14 2019 *)

for( n=5,999, n % precprime(sqrtint(n-1)) || print1(n","))

A327007 a(n) = number of iterations of f(x)=floor((x^2+n)/(2x)) starting at x=n to reach the value floor(sqrt(n)) (=A000196(n)).

Original entry on oeis.org

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

Offset: 1

Max Alekseyev, Aug 12 2019

nonn

Also, we have f(x) = floor((x + floor(n/x))/2).
Notice that f(n) = f(1) = floor((n+1)/2), and so the starting value x = 1 gives the same sequence.
Iterations f(f(...f(a))...) reach floor(sqrt(n)) for any starting integer a >= 1. They either stabilize to floor(sqrt(n)) or alternate between floor(sqrt(n)) and ceiling(sqrt(n)).

Cf. A000196, A327008, A327009, A327010.

{ A327007(n,a=n) = my(k = 0); while(1, my(b = (a+n\a)\2); if(b >= a,break); a = b; k++); k; }

A263096 Square roots of highly composite numbers, floored down: a(n) = A000196(A002182(n)).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 6, 6, 7, 10, 13, 15, 18, 26, 28, 35, 40, 50, 70, 86, 100, 122, 141, 158, 166, 212, 224, 235, 288, 332, 407, 470, 526, 576, 706, 744, 815, 848, 1039, 1200, 1470, 1697, 1898, 2079, 2546, 2684, 2940, 3287, 3796, 4158, 4649, 5694, 6062, 6575, 7826, 8573, 10500, 11068, 12125, 13556, 15653, 17147, 19172, 23480, 26426, 27113, 33206, 37373, 45772, 46961, 48248, 52853, 59092, 68233, 74746, 83568, 102350

Offset: 1

Antti Karttunen, Oct 10 2015

nonn

a(n) = number of strictly positive squares <= A002182(n).

Antti Karttunen, Table of n, a(n) for n = 1..1000 (based on the b-file of A002182 provided by _T. D. Noe_.)

Cf. A000196, A002182, A263097, A263098.

(define (A263096 n) (A000196 (A002182 n)))

a(n) = A000196(A002182(n)).

A278496 a(n) = A000196(A278494(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Nov 25 2016

nonn

Each n occurs A278495(n) times.

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

Cf. A000196, A002828, A255131, A278494, A278495.

(define (A278496 n) (A000196 (A278494 n)))

cp's OEIS Frontend

A334870 If n is a square, a(n) = A000196(n), and for nonsquare n, let p be the smallest prime dividing the squarefree part of n. Divide n by p and multiply by the product of all smaller primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A079051 Recamán variation: a(0) = 0; for n >= 1, a(n) = a(n-1) - f(n) if that number is positive and not already in the sequence, otherwise a(n) = a(n-1) + f(n), where f(n) = floor(sqrt(n)) (A000196).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A262689 a(n) = largest number k <= A000196(n) for which A002828(n-(k^2)) = A002828(n)-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A139004 Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A157942 Numbers n divisible by the largest prime <= sqrt(n), A007917(A000196(n)).

Views

Author

Keywords

Comments

Programs

Mathematica

PARI

A237273 Triangle read by rows: T(n,k) = k+m, if k < m and k*m = n, or T(n,k) = k, if k^2 = n. Otherwise T(n,k) = 0. With n>=1 and 1<=k<=A000196(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A157941 Numbers n divisible by the largest prime < sqrt(n), A007917(A000196(n-1)).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

A327007 a(n) = number of iterations of f(x)=floor((x^2+n)/(2x)) starting at x=n to reach the value floor(sqrt(n)) (=A000196(n)).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI