A260728 -id:A260728 - cp's OEIS frontend

A260730 Numbers n for which A065339(n) > A260728(n).

21, 33, 42, 57, 66, 69, 77, 84, 93, 105, 114, 129, 132, 133, 138, 141, 154, 161, 165, 168, 177, 186, 189, 201, 209, 210, 213, 217, 228, 231, 237, 249, 253, 258, 264, 266, 273, 276, 282, 285, 297, 301, 308, 309, 321, 322, 329, 330, 336, 341, 345, 354, 357, 372, 378, 381, 385, 393, 399, 402, 413, 417, 418, 420, 426, 429, 434, 437, 441, 453, 456, 462, 465, 469, 473, 474, 483, 489, 497, 498, 501, 506, 513, 516, 517, 525, 528, 532, 537, 546, 552

Offset: 1

Antti Karttunen, Aug 12 2015

nonn

Numbers n such that when the exponents in the prime factorization of A097706(n) are added in base-2 they produce at least one carry-bit. In other words, in that set of exponents {e1, e2, ..., en} there is at least one pair e_i, e_j that their binary representations have at least one 1-bit in the same position. (Here i and j are distinct as e_i and e_j are exponents of different primes, although e_i could be equal to e_j. See the examples.)

This differs from A119973 for the first time at n=30 where a(30)=231, term which is not present in A119973. Note that n=231 is the first position where the difference A065339(n) - A260728(n) > 1 as 231 = 3*7*11, a product of three distinct 4k+3 primes, thus A065339(231) = 3, while A260728(231) = 1.

			21 = 3^1 * 7^1 is present, because in its prime factors of the form 4k+3 (which are 3 and 7) the exponents 1 and 1 have at least one 1-bit in the same position, thus producing a carry-bit when summed in base-2.
63 = 3^2 * 7^1 is NOT present, because in its prime factors of the form 4k+3 the exponents 2 and 1 ("10" and "1" in binary) do NOT produce a carry-bit when summed in base-2, as those binary representations do not have any 1's in a common position.
189 = 3^3 * 7^1 is present, because in its prime factors of the form 4k+3 the exponents 3 and 1 ("11" and "1" in binary) have at least one 1-bit in the same position, thus producing a carry-bit when summed in base-2.

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

Cf. A065339, A260728, A097706, A119973.

A002828 Least number of squares that add up to n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Lagrange's "Four Squares theorem" states that a(n) <= 4.
It is easy to show that this is also the least number of squares that add up to n^3.
a(n) is the number of iterations in f(...f(f(n))...) to reach 0, where f(n) = A262678(n) = n - A262689(n)^2. Allows computation of this sequence without Lagrange's theorem. - Antti Karttunen, Sep 09 2016
It is also easy to show that a(k^2*n) = a(n) for k > 0: Clearly a(k^2*n) <= a(n) but for all 4 cases of a(n) there is no k which would result in a(k^2*n) < a(n). - Peter Schorn, Sep 06 2021

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1001 terms from T. D. Noe with corrections from Michel Marcus)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Square Number.

Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.

Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.

a002828 0 = 0  -- confessedly  /= 1, as sum [] == 0
a002828 n | a010052 n == 1 = 1
          | a025426 n > 0 = 2 | a025427 n > 0 = 3 | otherwise = 4
-- Reinhard Zumkeller, Feb 26 2015

with(transforms);
sq:=[seq(n^2, n=1..20)];
LAGRANGE(sq,4,120);
# alternative:
f:= proc(n) local F,x;
   if issqr(n) then return 1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return 2 fi;
   x:= n/4^floor(padic:-ordp(n,2)/2);
   if x mod 8 = 7 then 4 else 3 fi
end proc:
0, seq(f(n),n=1..200); # Robert Israel, Jun 14 2016
# next Maple program:
b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+(s-> `if`(s>n, 0, x*b(n-s, i)))(i^2))), x, 5), polynom)
    end:
a:= n-> ldegree(b(n, isqrt(n))):
seq(a(n), n=0..105);  # Alois P. Heinz, Oct 30 2021

SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; Table[SquareCnt[n], {n, 150}] (* T. D. Noe, Apr 01 2011 *)
sc[n_]:=Module[{s=SquaresR[Range[4],n]},If[First[s]>0,1,Length[ First[ Split[ s]]]+1]]; Join[{0},Array[sc,110]] (* Harvey P. Dale, May 21 2014 *)

istwo(n:int)=my(f);if(n<3,return(n>=0););f=factor(n>>valuation(n, 2)); for(i=1,#f[,1],if(bitand(f[i,2],1)==1&&bitand(f[i,1],3)==3, return(0)));1
isthree(n:int)=my(tmp=valuation(n,2));bitand(tmp,1)||bitand(n>>tmp,7)!=7
a(n)=if(isthree(n), if(issquare(n), !!n, 3-istwo(n)), 4) \\ Charles R Greathouse IV, Jul 19 2011, revised Mar 17 2022

from sympy import factorint
def A002828(n):
    if n == 0: return 0
    f = factorint(n).items()
    if not any(e&1 for p,e in f): return 1
    if all(p&3<3 or e&1^1 for p,e in f): return 2
    return 3+(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # Chai Wah Wu, Aug 01 2023

from sympy.core.power import isqrt
def A002828(n):
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        S = []
        r = isqrt(i)
        for j in range(1, r + 1):
            S.append(1 + dp[i - (j**2)])
        dp[i] = min(S)
    return dp[-1] # Darío Clavijo, Apr 21 2025

;; The first one follows Charles R Greathouse IV's PARI-code above:
(define (A002828 n) (cond ((zero? n) n) ((= 1 (A010052 n)) 1) ((= 1 (A229062 n)) 2) (else (+ 3 (A072401 n)))))
(define (A229062 n) (- 1 (A000035 (A260728 n))))
;; We can also compute this without relying on Lagrange's theorem. The following recursion-formula should be used together with the second Scheme-implementation of A262689 given in the Program section that entry:
(definec (A002828 n) (if (zero? n) n (+ 1 (A002828 (- n (A000290 (A262689 n)))))))
;; Antti Karttunen, Sep 09 2016

From Antti Karttunen, Sep 09 2016: (Start)
a(0) = 0; and for n >= 1, if A010052(n) = 1 [when n is a square], a(n) = 1, otherwise, if A229062(n)=1, then a(n) = 2, otherwise a(n) = 3 + A072401(n). [After Charles R Greathouse IV's PARI program.]
a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
a(n) = A053610(n) - A062535(n).
(End)

More terms from Arlin Anderson (starship1(AT)gmail.com)

A267116 Bitwise-OR of the exponents of primes in the prime factorization of n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Feb 03 2016

nonn

			For n = 4 = 2^2, bitwise-OR of 2 alone is 2, thus a(4) = 2.
For n = 6 = 2^1 * 3^1, when we take a bitwise-or of 1 and 1, we get 1, thus a(6) = 1.
For n = 24 = 2^3 * 3^1, bitwise-or of 3 and 1 ("11" and "01" in binary) gives "11", thus a(24) = 3.
For n = 210 = 2^1 * 3^1 * 5^1 * 7^1, bitwise-or of 1, 1, 1 and 1 gives 1, thus a(210) = 1.
For n = 720 = 2^4 * 3^2 * 5^1, bitwise-or of 4, 2 and 1 ("100", "10" and "1" in binary) gives 7 ("111" in binary), thus a(720) = 7.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Index entries for sequences computed from exponents in factorization of n

Cf. A001222, A003986, A007814, A028234, A067029.
Cf. A000290 (indices of even numbers).
Cf. A000037 (indices of odd numbers).
Nonunit terms of A005117, A062503, A113849 give the positions of ones, twos, fours respectively in this sequence.
Sequences with similar definitions: A260728, A267113, A267115 (bitwise-AND) and A268387 (bitwise-XOR of exponents).
Sequences with related analysis: A267114, A268374, A268375, A268376.
Sequences A088529, A136565 and A181591 coincide with a(n) for n: 2 <= n < 24.
A003961, A059896 are used to express relationship between terms of this sequence.
Related to A087207 via A225546.

read("transforms"):
A267116 := proc(n)
    local a,e ;
    a := 0 ;
    for e in ifactors(n)[2] do
        a := ORnos(a,op(2,e)) ;
    end do:
    a ;
end proc: # R. J. Mathar, Feb 16 2021

{0}~Join~Rest@ Array[BitOr @@ Map[Last, FactorInteger@ #] &, 120] (* Michael De Vlieger, Feb 04 2016 *)

a(n)=my(f = factor(n)); my(b = 0); for (k=1, #f~, b = bitor(b, f[k,2]);); b; \\ Michel Marcus, Feb 05 2016

a(n)=if(n>1, fold(bitor, factor(n)[,2]), 0) \\ Charles R Greathouse IV, Aug 04 2016

from functools import reduce
from operator import or_
from sympy import factorint
def A267116(n): return reduce(or_,factorint(n).values(),0) # Chai Wah Wu, Aug 31 2022

a(1) = 0; for n > 1: a(n) = A067029(n) OR a(A028234(n)). [Here OR stands for bitwise-or, A003986.]
Other identities and observations. For all n >= 1:
a(n) = A007814(n) OR A260728(n) OR A267113(n).
a(n) = A001222(n) - A268374(n).
A268387(n) <= a(n) <= A001222(n).
From Peter Munn, Jan 08 2020: (Start)
a(A059896(n,k)) = a(n) OR a(k).
a(A003961(n)) = a(n).
a(n^2) = 2*a(n).
a(n) = A087207(A225546(n)).
a(A225546(n)) = A087207(n).
(End)

A065339 Number of primes congruent to 3 modulo 4 dividing n (with multiplicity).

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Oct 29 2001

nonn

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

Cf. A001222, A007814, A065338, A005091, A007949, A083025 (analogous for 4k+1 primes), A097706, A378194.

Cf. A020639, A027746, A028234, A032742, A067029, A260728, A260730.

a065339 1 = 0
a065339 n = length [x | x <- a027746_row n, mod x 4 == 3]
-- Reinhard Zumkeller, Jan 10 2012

A065339 := proc(n)
    a := 0 ;
    for f in ifactors(n)[2] do
        if op(1,f) mod 4 = 3 then
            a := a+op(2,f) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Dec 16 2011

f[n_]:=Plus@@Last/@Select[If[n==1,{},FactorInteger[n]],Mod[#[[1]],4]==3&]; Table[f[n],{n,100}] (* Ray Chandler, Dec 18 2011 *)

A065339(n)=sum(i=1,#n=factor(n)~,if(n[1,i]%4==3,n[2,i]))  \\ M. F. Hasler, Apr 16 2012

;; using memoization-macro definec
(definec (A065339 n) (cond ((< n 3) 0) ((even? n) (A065339 (/ n 2))) (else (+ (/ (- (modulo (A020639 n) 4) 1) 2) (A065339 (A032742 n))))))
;; Antti Karttunen, Aug 14 2015

;; using memoization-macro definec
(definec (A065339 n) (cond ((< n 3) 0) ((even? n) (A065339 (/ n 2))) ((= 1 (modulo (A020639 n) 4)) (A065339 (A032742 n))) (else (+ (A067029 n) (A065339 (A028234 n))))))
;; Antti Karttunen, Aug 14 2015

a(n) = A001222(n) - A007814(n) - A083025(n).
(2^A007814(n)) * (3^a(n)) = A065338(n).
From Antti Karttunen, Aug 14 2015: (Start)
a(1) = a(2) = 0; thereafter, if n is even, a(n) = a(n/2), otherwise a(n) = ((A020639(n) mod 4)-1)/2 + a(n/A020639(n)). [Where A020639(n) gives the smallest prime factor of n.]
Other identities and observations. For all n >= 1:
a(n) = A007949(A065338(n)).
a(n) = A001222(A097706(n)).
a(n) >= A260728(n). [See A260730 for the positions of differences.] (End)
Totally additive with a(2) = 0, a(p) = 1 if p == 3 (mod 4), and a(p) = 0 if p == 1 (mod 4). - Amiram Eldar, Jun 17 2024

A097706 Part of n composed of prime factors of form 4k+3.

Original entry on oeis.org

1, 1, 3, 1, 1, 3, 7, 1, 9, 1, 11, 3, 1, 7, 3, 1, 1, 9, 19, 1, 21, 11, 23, 3, 1, 1, 27, 7, 1, 3, 31, 1, 33, 1, 7, 9, 1, 19, 3, 1, 1, 21, 43, 11, 9, 23, 47, 3, 49, 1, 3, 1, 1, 27, 11, 7, 57, 1, 59, 3, 1, 31, 63, 1, 1, 33, 67, 1, 69, 7, 71, 9, 1, 1, 3, 19, 77, 3, 79, 1, 81, 1, 83, 21

Offset: 1

Ralf Stephan, Aug 30 2004

Largest term of A004614 that divides n. - Peter Munn, Apr 15 2021

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Equivalent sequence for distinct prime factors: A170819.
Equivalent sequences for prime factors of other forms: A000265 (2k+1), A170818 (4k+1), A072436 (not 4k+3), A248909 (6k+1), A343431 (6k+5).
Range of values: A004614.
Positions of 1's: A072437.
Cf. also A065338, A065339, A260728, A286363.

a:= n-> mul(`if`(irem(i[1], 4)=3, i[1]^i[2], 1), i=ifactors(n)[2]):
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 09 2014

a[n_] := Product[{p, e} = pe; If[Mod[p, 4] == 3, p^e, 1], {pe, FactorInteger[n]}]; Array[a, 100] (* Jean-François Alcover, Jun 16 2015, updated May 29 2019 *)

a(n)=local(f); f=factor(n); prod(k=1, matsize(f)[1], if(f[k, 1]%4<>3, 1, f[k, 1]^f[k, 2]))

from sympy import factorint
from operator import mul
def a072436(n):
    f=factorint(n)
    return 1 if n == 1 else reduce(mul, [1 if i%4==3 else i**f[i] for i in f])
def a(n): return n/a072436(n) # Indranil Ghosh, May 08 2017

from math import prod
from sympy import factorint
def A097706(n): return prod(p**e for p, e in factorint(n).items() if p & 3 == 3) # Chai Wah Wu, Jun 28 2022

a(n) = n/A072436(n).
a(A004614(n)) = A004614(n).
a(A072437(n)) = 1.
a(n) = A000265(n)/A170818(n). - Peter Munn, Apr 15 2021

A286363 Least number with the same prime signature as {the largest divisor of n with only prime factors of the form 4k+3} has: a(n) = A046523(A097706(n)).

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 1, 4, 1, 2, 2, 1, 2, 2, 1, 1, 4, 2, 1, 6, 2, 2, 2, 1, 1, 8, 2, 1, 2, 2, 1, 6, 1, 2, 4, 1, 2, 2, 1, 1, 6, 2, 2, 4, 2, 2, 2, 4, 1, 2, 1, 1, 8, 2, 2, 6, 1, 2, 2, 1, 2, 12, 1, 1, 6, 2, 1, 6, 2, 2, 4, 1, 1, 2, 2, 6, 2, 2, 1, 16, 1, 2, 6, 1, 2, 2, 2, 1, 4, 2, 2, 6, 2, 2, 2, 1, 4, 12, 1, 1, 2, 2, 1, 6, 1, 2, 8, 1, 2, 2, 2, 1, 6, 2, 1, 4, 2, 2, 2

Offset: 1

Antti Karttunen, May 08 2017

nonn

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

Cf. A046523, A097706, A286361, A286364, A286365.

Cf. also A065338, A065339, A260728, A267099.

from sympy import factorint
from operator import mul
def P(n):
    f = factorint(n)
    return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a072436(n):
    f = factorint(n)
    return 1 if n == 1 else reduce(mul, [1 if i%4==3 else i**f[i] for i in f])
def a(n): return a046523(n/a072436(n)) # Indranil Ghosh, May 09 2017

(define (A286363 n) (A046523 (A097706 n)))

a(n) = A046523(A097706(n)).

a(n) = A286361(A267099(n)).

A267113 Bitwise-OR of the exponents of all 4k+1 primes in the prime factorization of n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Feb 03 2016

nonn

			For n = 65 = 5 * 13 = (4+1)^1 * ((3*4)+1)^1, bitwise-or of 1 and 1 is 1, thus a(65) = 1.

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

Cf. A170818, A267116, A260728.
Cf. A004144 (indices of zeros), A009003 (of nonzeros).
Differs from both A046080 and A083025 for the first time at n=65, which here a(65) = 1.

a(n) = A267116(A170818(n)).
Other identities. For all n >= 0:
a(n) = a(A170818(n)). [The result depends only on the prime factors of the form 4k+1.]
a(n) <= A083025(n).

cp's OEIS Frontend

A260730 Numbers n for which A065339(n) > A260728(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A002828 Least number of squares that add up to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A267116 Bitwise-OR of the exponents of primes in the prime factorization of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A065339 Number of primes congruent to 3 modulo 4 dividing n (with multiplicity).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Scheme

Scheme

Formula

A097706 Part of n composed of prime factors of form 4k+3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A286363 Least number with the same prime signature as {the largest divisor of n with only prime factors of the form 4k+3} has: a(n) = A046523(A097706(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

Formula

A267113 Bitwise-OR of the exponents of all 4k+1 primes in the prime factorization of n.