Even and Odd kinds

Question

Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of even kind. Likewise, we say \$n\$ is of odd kind of the prime factorisation of \$n\$ has an odd number of integers, such as \$18 = 2 \times 3 \times 3\$. Note that as the prime factorisation of \$1\$ contains \$0\$ primes, it is of even kind.

Let \$E(n)\$ be the count of positive integers of even kind less than or equal to \$n\$, and \$O(n)\$ be the count of positive integers of odd kind less than or equal to \$n\$. For example, for \$n = 14\$, we have

\$E(14) = 6\$ (\$1, 4, 6, 9, 10, 14\$), and
\$O(14) = 8\$ (\$2, 3, 5, 7, 8, 11, 12, 13\$)

You are to write a program which takes some positive integer \$n \ge 1\$ as input, and outputs the two values \$E(n)\$ and \$O(n)\$. You may input and output in any convenient method, and you may output the two outputs in any format that consistently presents the values (e.g. you cannot output one in unary and another in decimal), and that clearly distinguishes between the two (typically, has some kind of obvious delimiter).

This is a code-golf challenge, so the shortest code in bytes wins.

Test cases

n -> [E(n), O(n)]
1 -> [1, 0]
2 -> [1, 1]
3 -> [1, 2]
4 -> [2, 2]
5 -> [2, 3]
6 -> [3, 3]
7 -> [3, 4]
8 -> [3, 5]
9 -> [4, 5]
10 -> [5, 5]
11 -> [5, 6]
12 -> [5, 7]
13 -> [5, 8]
14 -> [6, 8]
15 -> [7, 8]
16 -> [8, 8]
17 -> [8, 9]
18 -> [8, 10]
19 -> [8, 11]
20 -> [8, 12]

Diamond coated brownie points for beating/matching my 7 byte Jelly answer — caird coinheringaahin g, Oct 21, 2022 at 1:17
Trivia: Polya conjecture states that E(n) <= O(n) for all n >= 2. This conjecture was proven to be false, with the smallest counterexample being n = 906,150,257. — Bubbler, Oct 21, 2022 at 7:43
@cairdcoinheringaahing Can we return only one value for 1? The Japt answer does that but I don't feel like it's right (even though that would make things simpler for me) — Fatalize, Oct 21, 2022 at 14:22
@Fatalize No, you must return a 1 and a 0. If, however, you are outputting only unary, then outputting an empty string is okay (as that's 0 in unary), but otherwise, there should be two clear values output. — caird coinheringaahin g, Oct 21, 2022 at 15:09
Trivia on the trivia: Pólya never conjectured "Pólya's conjecture" (more accurately called "Pólya's problem")—instead he showed that it would imply the Riemann Hypothesis if it were true. — Greg Martin, Oct 22, 2022 at 2:31

Jonah · Accepted Answer · 2022-10-21 01:35:47Z

6

J, 19 bytes

(-,])1#.2|1#@q:@+i.

Try it online!

1...+i. 1 2 ... n
#@q: Length # of prime factors q: of each
1#.2| Sum of even lengths
(-,]) Input minus that sum - catted with , that sum ]

edited Oct 21, 2022 at 1:35

answered Oct 21, 2022 at 1:24

Jonah

33k4 gold badges38 silver badges92 bronze badges

Add a comment |

naffetS · Accepted Answer · 2022-10-21 01:38:49Z

5

Jelly, 8 bytes

RÆE§ḂSṄạ

Try it online!

RÆE§ḂSṄạ
R         - Range [1, input]
 ÆE       - For each, get a list of the prime exponents
   §      - Sum each
    Ḃ     - Modulo each by 2
     S    - Sum
      Ṅ   - Print (with a trailing newline)
       ạ  - Get the absolute difference between this and the input (also implicitly printed)

edited Oct 21, 2022 at 1:38

answered Oct 21, 2022 at 1:30

naffetS

12.2k2 gold badges17 silver badges48 bronze badges

\$\begingroup\$ Nice! You can still remove a byte tho :P \$\endgroup\$
– caird coinheringaahin g ♦
Oct 21, 2022 at 1:46

Add a comment |

alephalpha · Accepted Answer · 2022-10-21 01:35:38Z

4

PARI/GP, 31 bytes

n->sum(i=1,n,I^(bigomega(i)%2))

Attempt This Online!

Outputs a complex number where the real part is \$E(n)\$ and the imaginary part is \$O(n)\$.

answered Oct 21, 2022 at 1:35

alephalpha

46.5k7 gold badges61 silver badges172 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-10-21 08:44:44Z

4

05AB1E, 8 7 bytes

LÓOÉ1Ý¢

Try it online or verify all test cases.

Explanation:

-1 byte by realizing that: amount of prime factors of \$x\$ == sum(exponents of \$x\$'s prime factorization): see that they are the same here.

L        # Push a list in the range [1, (implicit) input]
 Ò       # Get the prime exponents of each inner integer
  O      # Sum each inner list together
   É     # Check for each sum whether it's odd
    1Ý   # Push pair [0,1]
      ¢  # Count the occurrences of 0 and 1 in the list
         # (after which the result is output implicitly)

edited Oct 21, 2022 at 8:44

answered Oct 21, 2022 at 8:34

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

2

\$\begingroup\$ Tounge-in-cheek, but since the question explicitly mentioned the possibility of unary output: 5 bytes with unary output of zero-digits for E(n) and one-digits for O(n)... \$\endgroup\$
– Dominic van Essen
Oct 21, 2022 at 11:16
\$\begingroup\$ @DominicvanEssen Nice bending of the rules. :D \$\endgroup\$
– Kevin Cruijssen
Oct 21, 2022 at 11:19

Add a comment |

Arnauld · Accepted Answer · 2022-10-21 08:47:17Z

JavaScript (ES6), 71 bytes

f=(n,a=[0,0])=>n?f(n-1,a,a[(g=_=>k>n?0:n%k?g(k++):1^g(n/=k))(k=2)]++):a

Try it online!

Commented

f = (                 // f is a recursive function taking:
  n,                  //   n = input
  a = [0, 0]          //   a[] = output array
) =>                  //
n ?                   // if n is not equal to 0:
  f(                  //   do a recursive call:
    n - 1,            //     decrement n
    a,                //     pass a[]
    a[                //     update a[]:
      ( g =           //       g is a recursive function
        _ =>          //       which ignores its parameter
        k > n ?       //       if k is greater than n:
          0           //         stop the recursion
        :             //       else:
          n % k ?     //         if k is not a divisor of n:
            g(k++)    //           increment k and do a recursive call
          :           //         else:
            1 ^       //           invert the result
            g(n /= k) //           divide n by k and do a recursive call
      )(k = 2)        //       initial call to g, starting with k = 2
    ]++               //     increment a[0] or a[1], depending on the
                      //     parity of the number of prime divisors of n
  )                   //   end of recursive call
:                     // else:
  a                   //   return a[]

Aiden Chow · Accepted Answer · 2022-10-31 07:15:38Z

Desmos, 101 97 bytes

f(K)=∑_{k=1}^Kmod([1,0]+∑_{n=2}^klog_n(gcd(n^{ceil(log_nk)},k))sign(∏_{a=3}^nmod(n,a-1)),2)

Output is the list \$[E(n),O(n)]\$. It will fail on larger values due to floating point inaccuracies, but I've tested values such as \$1000\$ and it gives the right output, so it's pretty much a nonissue.

Try It On Desmos!

Try It On Desmos! - Prettified

A shorter version of the above code technically works, but it fails for values greater than \$15\$ due to floating point errors (so it doesn't even pass all the test cases):

88 84 bytes

f(K)=∑_{k=1}^Kmod([1,0]+∑_{n=2}^klog_n(gcd(n^k,k))sign(∏_{a=3}^nmod(n,a-1)),2)

Try It On Desmos!

Try It On Desmos! - Prettified

naffetS · Accepted Answer · 2022-10-21 01:34:27Z

3

Vyxal `o`, 8 bytes

ɾǐvL∷∑…ε

Try it Online!

edited Oct 21, 2022 at 1:34

answered Oct 21, 2022 at 1:26

naffetS

12.2k2 gold badges17 silver badges48 bronze badges

Add a comment |

lyxal · Accepted Answer · 2022-10-21 04:18:45Z

3

Vyxal, 8 bytes

'ǐ₂;L~ε"

Try it Online!

A flagless 8 byter that uses a method that is a little different to the other answer.

7 bytes using this approach with a flag:

Vyxal `o`, 7 bytes

'ǐ₂;L…ε

Try it Online!

answered Oct 21, 2022 at 4:18

lyxal

32.5k2 gold badges56 silver badges138 bronze badges

Add a comment |

Jordan · Accepted Answer · 2022-10-21 17:25:11Z

3

Ruby, 72 66 bytes

-6 bytes thanks to Dingus

->n{[e=(1..n).map{|m|m.prime_division.sum{_2}}.count{_1%2<1},n-e]}

Attempt This Online!

edited Oct 21, 2022 at 17:25

answered Oct 21, 2022 at 2:30

Jordan

9,7261 gold badge30 silver badges47 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-10-22 20:57:50Z

3

Factor + `math.primes.factors`, 58 50 bytes

[ dup [1,b] [ factors length odd? ] count tuck - ]

Try it online!

dup Create an extra copy of the input.
[1,b] Create a range from one to the input (inclusive).
[ ... ] count Count the number of elements in the range for which [ ... ] returns true.
factors length odd? Does it have an odd number of factors?
tuck - Subtract the result from the input non-destructively. (Implicit multiple return)

edited Oct 22, 2022 at 20:57

answered Oct 21, 2022 at 10:05

chunes

22.7k3 gold badges21 silver badges51 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2022-10-25 09:00:14Z

Japt, 12 bytes

Had to sacrifice 2 bytes to handle 1 :\

2Æõk è_Ê¤Ì¦X

Try it

2Æõk è_Ê¤Ì¦X     :Implicit input of integer U
2Æ               :Map each X in the range [0,2)
  õ              :  Range [1,U]
   k             :  Prime factors of each
     è           :  Count the elements that return true
      _          :  When passed through the following function
       Ê         :    Length
        ¤        :    To binary string
         Ì       :    Last character
          ¦X     :    Not equal to X?

hakr14 · Accepted Answer · 2022-10-21 05:53:39Z

2

Mathematica, 40 bytes

Length/@PrimeOmega@Range@#~GroupBy~OddQ&

View it on Wolfram Cloud!

Output in the form <|False->E(n),True->O(n)|>.

answered Oct 21, 2022 at 5:53

hakr14

4,9641 gold badge10 silver badges18 bronze badges

1

\$\begingroup\$ For n=1, outputs just <|False->1|>. \$\endgroup\$
– Bubbler
Oct 21, 2022 at 8:09
\$\begingroup\$ As noted by Bubbler, the output format doesn't work for n = 1, as it should include both E(n) and O(n) \$\endgroup\$
– caird coinheringaahin g ♦
Oct 21, 2022 at 11:41

Add a comment |

Dominic van Essen · Accepted Answer · 2022-10-21 12:47:49Z

2

R, 79 bytes

\(n)c(y<-sum(sapply(1:n,f<-\(n,p=2)sum(x<-!n%%p,if(n>1)f(n/p^x,p+!x))%%2)),n-y)

Attempt This Online!

Returns O(n), E(n).

Helper function f returns the number of prime factors, f%%2 returns whether-or-not this is odd: f<-\(n,p=2)sum(x<-!n%%p,if(n>1)f(n/p^x,p+!x))

edited Oct 21, 2022 at 12:47

answered Oct 21, 2022 at 12:41

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-10-21 22:50:05Z

Retina 0.8.2, 63 bytes

.+
$*
M!&`.+
+%`^(2*(1+))\2+$
2$1
22|¶

O`2?1
(1)+(21)*
$#1 $#2

Try it online! Link is to test suite that outputs the results for 1..n. Explanation:

.+
$*

Convert to unary.

M!&`.+

List all the numbers from n down to 1.

+%`^(2*(1+))\2+$
2$1

Count the number of prime factors of each number, using repeated 2s as the count. This leaves a lone trailing 1 once all of the prime factors have been counted.

22|¶

Take the parity of the counts of prime factors, so that 1 means that it had an even number and 21 means that it had an odd number, and join all of the results together.

O`2?1

Sort the 1s and 21s separately to make them easier to count.

(1)+(21)*
$#1 $#2

Count the number of 1s and 21s.

Aiden Chow · Accepted Answer · 2022-10-26 06:01:18Z

2

GeoGebra, 66 bytes

InputBox(n
a=Sum(Zip(Mod(Length(PrimeFactors(a)),2),a,1...n
ai+n-a

Try It On GeoGebra!

Output is in the form \$E(n)+O(n)i\$.

answered Oct 26, 2022 at 6:01

Aiden Chow

12.7k1 gold badge14 silver badges53 bronze badges

Add a comment |

CursorCoercer · Accepted Answer · 2022-11-01 18:51:39Z

2

Pyth, 10 bytes

aBsm.&1lPh

Try it online!

Outputs [O(n), E(n)].

Explanation

aB            bifurcate the absolute difference of implicit eval(input()) and
  s           the sum of
   m          map over implicit range(eval(input()))
    .&1       modulo 2 (bitwise and 1)
       l      the length of 
        P     the list of the prime factors of
         h    1 + implicit map lambda variable

answered Nov 1, 2022 at 18:51

CursorCoercer

3,9779 silver badges18 bronze badges

Add a comment |

Ashlin Harris · Accepted Answer · 2022-11-02 14:59:04Z

[Julia 1.1], 92 bytes

using Primes
~N=(X=map(n->sum([b for (a,b)=factor(n)]),1:N);[sum(X.%2 .==0),sum(isodd.(X))])

Julia 1.0 appears to be supported by the package Primes.jl, but I haven't been able to import it successfully. Here is the output in Julia 1.1:

julia> VERSION
v"1.1.1"

julia> using Primes

julia> ~N=(X=map(n->sum([b for (a,b)=factor(n)]),1:N);[sum(X.%2 .==0),sum(isodd.(X))])
~ (generic function with 1 method)

julia> map(x -> println(lpad(x,2) * " -> $(~x)"), 1:20);
 1 -> [1, 0]
 2 -> [1, 1]
 3 -> [1, 2]
 4 -> [2, 2]
 5 -> [2, 3]
 6 -> [3, 3]
 7 -> [3, 4]
 8 -> [3, 5]
 9 -> [4, 5]
10 -> [5, 5]
11 -> [5, 6]
12 -> [5, 7]
13 -> [5, 8]
14 -> [6, 8]
15 -> [7, 8]
16 -> [8, 8]
17 -> [8, 9]
18 -> [8, 10]
19 -> [8, 11]
20 -> [8, 12]

This solution could be adapted without Primes in Julia 0.4, when factor was still part of base Julia.

Fatalize · Accepted Answer · 2022-10-21 14:30:15Z

1

Brachylog, 15 bytes

⟦₁{ḋl%₂}ᵍlᵐĊ|;0

Try it online!

Explanation

4 additional bytes needed at the end to deal with the special case of 1.

⟦₁                  Range [1, ..., Input]
  {    }ᵍ           Group by:
   ḋl%₂                 Length of prime decomposition mod 2
         lᵐ         Map length
            Ċ|;0    Output must have 2 elements; otherwise (Input = 1), Output = [Input, 0]

answered Oct 21, 2022 at 14:30

Fatalize

38.4k5 gold badges67 silver badges160 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-10-21 23:11:08Z

Charcoal, 40 bytes

Ｆ…·¹Ｎ«≔⁰θＷΦι¬﹪ι⁺²λ«≧÷⁺²⌊κι≦¬θ»⊞υθ»ＩＥ²№υι

Try it online! Link is to verbose version of code. Explanation:

Ｆ…·¹Ｎ«

Loop from 1 up to and including n.

≔⁰θ

Assume even kind.

ＷΦι¬﹪ι⁺²λ«

While the current value has any nontrivial factors: ...

≧÷⁺²⌊κι

... divide it by the lowest such factor, and...

≦¬θ

... flip between even and odd kind.

»⊞υθ

Save the kindness of the current value.

»ＩＥ²№υι

Output the counts of even and odd kindness.

Cliff · Accepted Answer · 2022-10-31 12:53:38Z

Ohm v2, 11 bytes

@€olé;ΣD³a«

Try it online!

Returns a list of [E(n), O(n)]. Note that Ohm v2 formats numbers a little weirdly when they are in a list, but they are definitely the right numbers.

Explained

@€olé;ΣD³a«
@            # Push a range from 1 to the input to the stack
 €   ;       # To each item in the range from before:
  ol         # Get the length of the full prime factorization of the item
    é        # and then push whether the length is even
      ΣD     # Push two copies of the sum of that list - the first copy is how many numbers are E(n), and the second will be used to calculate how many numbers are O(n)
        ³a   # Get the absolute difference of the input and the E(n) count
          «  # Pair into a list

chunes · Accepted Answer · 2023-02-18 20:37:29Z

1

Arturo, 52 bytes

$[n][x:∑map 1..n=>[%size factors.prime&2]@[n-x,x]]

Try it

answered Feb 18 at 20:37

chunes

22.7k3 gold badges21 silver badges51 bronze badges

Add a comment |

The Thonnu · Accepted Answer · 2023-02-19 15:52:53Z

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.70 bytes

R1+Zh.S2%10dc

Attempt This Online! Port of Kevin Cruijssen's 05AB1E answer.

Thunno, \$ 16 \log_{256}(96) \approx \$ 13.17 bytes

DR1+Zh.S2%SDZKAD

Attempt This Online! Port of Steffan's Jelly answer.

Explanations

R1+Zh.S2%10dc  # Implicit input
R1+            # Push range(1, input + 1)
   Zh          # Prime factor exponents
     .S2%      # Sum mod 2 of each
         10dc  # Count 1s and 0s

DR1+Zh.S2%SDZKAD  # Implicit input
DR1+              # Duplicate and push range(1, input + 1)
    Zh            # Prime factor exponents
      .S2%        # Sum mod 2 of each
          SDZK    # Sum and print without popping
              AD  # Absolute difference with input

Stack Exchange Network

Even and Odd kinds

Test cases

22 Answers 22

J, 19 bytes

Jelly, 8 bytes

PARI/GP, 31 bytes

05AB1E, 8 7 bytes

JavaScript (ES6), 71 bytes

Commented

Desmos, 101 97 bytes

88 84 bytes

Vyxal `o`, 8 bytes

Vyxal, 8 bytes

Vyxal `o`, 7 bytes

Ruby, 72 66 bytes

Factor + `math.primes.factors`, 58 50 bytes

Japt, 12 bytes

Mathematica, 40 bytes

R, 79 bytes

Retina 0.8.2, 63 bytes

GeoGebra, 66 bytes

Pyth, 10 bytes

Explanation

[Julia 1.1], 92 bytes

Brachylog, 15 bytes

Explanation

Charcoal, 40 bytes

Ohm v2, 11 bytes

Explained

Arturo, 52 bytes

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.70 bytes

Thunno, \$ 16 \log_{256}(96) \approx \$ 13.17 bytes

Explanations

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
number-theory
primes
or ask your own question.

Hot Network Questions

Even and Odd kinds

Test cases

22 Answers 22

J, 19 bytes

Jelly, 8 bytes

PARI/GP, 31 bytes

05AB1E, 8 7 bytes

JavaScript (ES6), 71 bytes

Commented

Desmos, 101 97 bytes

88 84 bytes

Vyxal o, 8 bytes

Vyxal, 8 bytes

Vyxal o, 7 bytes

Ruby, 72 66 bytes

Factor + math.primes.factors, 58 50 bytes

Japt, 12 bytes

Mathematica, 40 bytes

R, 79 bytes

Retina 0.8.2, 63 bytes

GeoGebra, 66 bytes

Pyth, 10 bytes

Explanation

[Julia 1.1], 92 bytes

Brachylog, 15 bytes

Explanation

Charcoal, 40 bytes

Ohm v2, 11 bytes

Explained

Arturo, 52 bytes

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.70 bytes

Thunno, \$ 16 \log_{256}(96) \approx \$ 13.17 bytes

Explanations

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequencenumber-theoryprimes or ask your own question.

Related

Hot Network Questions

Vyxal `o`, 8 bytes

Vyxal `o`, 7 bytes

Factor + `math.primes.factors`, 58 50 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
number-theory
primes
or ask your own question.