A066376 Number of [*]-divisors d <= n such that there is another [*]-divisor d' < n with d [*] d' = n.

0, 1, 1, 2, 1, 3, 2, 3, 1, 3, 1, 5, 1, 5, 4, 4, 1, 3, 1, 5, 2, 3, 1, 7, 1, 3, 3, 8, 1, 9, 7, 5, 1, 3, 1, 5, 1, 3, 1, 7, 1, 5, 1, 5, 3, 3, 3, 9, 1, 3, 3, 5, 1, 7, 3, 11, 1, 3, 3, 14, 3, 15, 13, 6, 1, 3, 1, 5, 1, 3, 1, 7, 2, 3, 1, 5, 1, 3, 1, 9, 1, 3, 1, 8, 4, 3, 1, 7, 1, 7, 3, 5, 1, 7, 5, 11, 1

Offset

1,4

Comments

Define [+] to be binary bitwise inclusive-OR and let [*] denote the shift-and-[+] product. ([+] is usually simply called OR.) Note that [*] is commutative, associative, and distributes over [+]. If x [*] y = z, we say x and y are [*]-divisors of z.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Example

14 has 5 [*]-divisors: 1, 2, 3, 6, 7, since for example 2 [*] 7 = 10 [*] 111 = 1110 OR 0000 = 1110; and 3 [*] 6 = 11 [*] 110 = 1100 OR 0110 = 1110.

Prog

(Haskell)
import Data.Bits (Bits, (.|.), shiftL, shiftR)
a066376 :: Int -> Int
a066376 n = length [d | d <- [1..n-1], any ((== n) . (orm d)) [1..n]] where
   orm 1 v = v
   orm u v = orm (shiftR u 1) (shiftL v 1) .|. if odd u then v else 0
-- Reinhard Zumkeller, Mar 01 2013

Crossrefs

Cf. A067139 ("primes").

See A003986 for a table of [+] sums, A067138 for a table of [*] products.

Sequence in context: A363654 A189231 A107337 * A151682 A318928 A159918

Adjacent sequences: A066373 A066374 A066375 * A066377 A066378 A066379

Keyword

nonn,easy,nice

Author

Marc LeBrun, Dec 22 2001

Extensions

Edited by N. J. A. Sloane, Dec 13 2021

Name corrected by Sean A. Irvine, Oct 10 2023

Status

approved