login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058764 Smallest number x such that cototient(x) = 2^n. 8
2, 4, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

Since the cototient of 3*2^n is 2^(n+1), upper bounds are given by A007283(n-1). - R. J. Mathar, Oct 13 2008

A058764(n+1) is the number of different walks with n steps in the graph G = ({1,2,3,4}, {{1,2}, {2,3}, {3,4}}). - Aldo González Lorenzo, Feb 27 2012

LINKS

Jud McCranie, Table of n, a(n) for n = 0..45

FORMULA

a(n) = min { x | A051953(x) = 2^n }.

a(n) = (if n>1 then 3 else 4)*2^(n-1) = A007283(n-1) for n>1. (Conjectured.) - M. F. Hasler, Nov 10 2016

EXAMPLE

a(5) = 48, cototient(48) = 48-Phi(48) = 48-16 = 32. For n>2, a(n) = 3*2^(n-1); largest solutions = 2^(n+1). Prime factors of solutions: 2 and Mersenne-primes were found only.

MATHEMATICA

Function[s, Flatten@ Map[First@ Position[s, #] &, 2^Range[0, Floor@ Log2@ Max@ s]]]@ Table[n - EulerPhi@ n, {n, 10^7}] (* Michael De Vlieger, Dec 17 2016 *)

PROG

(PARI) a(n) = {x = 1; while(x - eulerphi(x) != 2^n, x++); x; } \\ Michel Marcus, Dec 11 2013

(PARI) a(n) = if(n>1, 3, 4)<<(n-1) \\ M. F. Hasler, Nov 10 2016

CROSSREFS

Cf. A051953, A053579, A053650.

Cf. A042950. - R. J. Mathar, Jan 30 2009

Cf. A007283.

Sequence in context: A095849 A094783 * A087009 A168263 A162936 A036484

Adjacent sequences:  A058761 A058762 A058763 * A058765 A058766 A058767

KEYWORD

nonn,hard

AUTHOR

Labos Elemer, Jan 02 2001

EXTENSIONS

Edited by M. F. Hasler, Nov 10 2016

a(27)-a(31) from Jud McCranie, Jul 13 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 18 18:54 EST 2018. Contains 318243 sequences. (Running on oeis4.)