OPINION
GWIN, District Judge.Michael Melchor appeals a 360-month sentence imposed by the district court for receiving child pornography. Melchor argues that his sentence, which exceeded the Sentencing Guidelines range of 210-262 months, is substantively unreasonable. For the reasons below, we VACATE Mel-chor’s sentence and REMAND for resen-tencing.
I. BACKGROUND
In August 2011, an Oregon woman reported to police that her 12-year-old daughter J.S. was using Facebook to communicate with 36-year-old Melchor. Mel-chor and J.S. met while playing an online game and became Facebook friends shortly thereafter. The online contact between *446Melchor and J.S. was sexual in nature. Melchor described in detail engaging in sexual intercourse with J.S. and talked about shaving J.S.’s pubic hair.
The police discovered that Melchor, a previously registered sex offender, resided in Grand Rapids, Michigan, and obtained a search warrant. Upon searching Mel-chor’s home, the police discovered a laptop computer, a desktop computer, and thumb drives, all containing child pornography. Melchor candidly admits his attraction to young girls.
On September 8, 2009, a grand jury returned a superseding indictment charging Melchor with two counts: (1) knowingly receiving child pornography in the form of digital images using any means or facility of interstate commerce, in violation of 18 U.S.C. § 2252A(a)(2)(A), (b)(1); and (2) knowingly possessing child pornography shipped or transported in interstate commerce in violation of 18 U.S.C. § 2252A(a)(5)(B).
After reaching a plea agreement, Mel-chor pleaded guilty to Count One. In exchange, the Government moved to dismiss Count 2 and agreed not to bring charges for Melchor’s conduct with J.S. After his acceptance of responsibility and after adjustments for specific offense characteristics, the Presentence Investigation Report (PSR) recommended Melchor’s final offense level to be 35. The calculation included a five-level enhancement under U.S.S.G. § 2G2.2(b)(5) for engaging in a pattern of activity involving sexual abuse or exploitation of a minor.
The PSR based that enhancement on three prior documented instances of Mel-chor’s sexual abuse or exploitation of a minor: (1) Melchor’s admission of sexually abusive contact with his two-year-old sister when he was a teenager; (2) Melchor’s October 2001 conviction for interstate transport of a minor with criminal sexual intent; and (3) Melchor’s December 2001 conviction for traveling in interstate commerce for the purposes of engaging in a sexual act with a minor. The PSR did not rely upon Melchor’s conduct with J.S. for the enhancement.
An offense level of 35, paired with Mel-chor’s criminal history — yields a Guideline recommendation of 210-262 months. But, the PSR recommended a sentence of 480 months — more than double the Guideline recommended range and 218 months above the upper Guideline range. The PSR gave two reasons for this recommendation: (1) the Guidelines did not account for Mel-chor’s conduct with J.S. and (2) Melchor was not amenable to rehabilitation.
At Melchor’s sentencing, the Government recommended a sentence within the Guideline range, while Melchor argued for a sentence below or within the Guideline range. Adopting the reasoning of the PSR, the district court imposed a sentence of 360 months, ninety-eight months above the high end of Melchor’s Guidelines range. Melchor filed a timely notice of appeal.
II. ANALYSIS
Melchor says that his sentence is substantively unreasonable. “A sentence may be considered substantively unreasonable when the district court selects the sentence arbitrarily, bases the sentence on impermissible factors, fails to consider pertinent § 3553(a) factors or gives an unreasonable amount of weight to any pertinent factor.” United States v. Collington, 461 F.3d 805, 808 (6th Cir.2006) (internal citations omitted). The sentence must also “be proportionate to the seriousness of the circumstances of the offense and offender, and sufficient but not greater than necessary, to comply with the purposes of § 3553(a).” United States v. Vowell, 516 *447F.3d 503, 512 (6th Cir.2008) (internal citations omitted).
We review sentences for reasonableness under an abuse of discretion standard. United States v. Penson, 526 F.3d 331, 336 (6th Cir.2008). A sentence within the Guidelines range is presumptively reasonable. Collington, 461 F.3d at 808. A sentence outside the Guidelines range, however, is not presumptively unreasonable. United States v. Vonner, 516 F.3d 382, 389 (6th Cir.2008). For a sentence outside the Guidelines range, we may consider
the extent of the deviation, but must give due deference to the district court’s decision that the § 3553(a) factors, on a whole, justify the extent of the variance. The fact that [we] might reasonably ... [have] concluded that a different sentence was appropriate is insufficient to justify reversal of the district court.
Gall v. United States, 552 U.S. 38, 51, 128 S.Ct. 586, 169 L.Ed.2d 445, (2007).
Melchor says: (1) that the district court erred in imposing an upward variance based on Melchor’s likelihood for recidivism; and (2) that the district court erred in imposing an upward variance based on Melchor’s conduct with J.S. We address his two arguments in turn.
A. Melchor’s Potential for Rehabilitation
First, Melchor says that it was improper for the district court to impose an upward variance based on its assessment that Melchor had a high risk for recidivism. This assessment was partially based on Melchor’s own statements at his allocution. Melchor admitted his inappropriate attraction to children and noted that treatment programs had not been successful for him in the past. If required to attend treatment again, Melchor said that he will “just put [his attractions] on the back burner in [his] mind.” He furthermore conceded that “[t]he only way [he’s] willing to change is on [his] own ... but there’s no telling how long that’s going to take.... ” In arguing that the district court erred in its reliance upon Mechor’s risk of recidivism, Melchor says that recidivism is a trait common among sexual offenders, that his candid statements are a reflection of this common issue, and that they do not warrant an increase in his sentence.
Melchor, however, cites no compelling support for this argument. The one case that he cites to, United States v. Poynter, 495 F.3d 349 (6th Cir.2007), is readily distinguishable. In Poynter, the district court sentenced a sex offender to sixty years in prison — forty years above the top of the applicable sentencing Guidelines. Id. at 353-354. In assigning such a large variance the district court “left ... little room to distinguish between Poynter and other sex offenders” in determining that he was at high risk of re-offending. Id. at 354. In contrast, Melchor’s sentence is ninety-eight months above the top of the Guidelines range, not forty years. Moreover, the district court found Melchor was likely to reoffend because Melchor himself admitted that he was unlikely to change his behavior.
Under 18 U.S.C. § 3553(a), the district court should consider deterrence and protection of the public when assigning a sentence. 18 U.S.C. § 3553(a) (2010). And this Court has not hesitated to affirm reasonable upward variances based on potential for recidivism in the past. See, e.g., United States v. Matheny, 450 F.3d 633, 641 (6th Cir.2006) (“The district court’s six month’s enhancement was not an unreasonable way to ensure that [the defendant] understood that ... recidivism is not acceptable”); United States v. Williams, 214 Fed.Appx. 552, 556 (6th Cir.2007) (affirming an upward variance in light of the *448defendants’ continuing propensity for violence); Burton, 241 Fed.Appx. at 820-21 (affirming an upward variance based on defendant’s criminal history and high potential for recidivism). Melchor has said himself that he is a continuing threat to children and that there is little hope for his rehabilitation. Thus, the district court did not abuse its discretion when it found that Melchor’s potential for recidivism warranted an upward variance.
B. Melchor’s Conduct with J.S.
Second, Melchor says that the district court improperly double-counted his conduct with J.S. He says that his conduct with J.S. was already covered by the five-level increase he had received under the Guidelines. Thus, he says the district court erred when it varied upward, based in part, on its finding that the Guidelines did not account for that conduct. Melchor is correct that a sentence is substantively unreasonable where the district court varies substantially from the Guidelines, yet fails to identify a compelling justification for the variance. See United States v. Aleo, 681 F.3d 290 (6th Cir.2012). A district court’s justification is not compelling if the “guidelines took into account the very factors the judge said that they did not.” Id. at 301.
At the sentencing, the district court imposed a five-level enhancement for Mel-chor’s engaging in a pattern of activity involving the sexual abuse or exploitation of a minor. The application notes to Guideline § 2G2.2(b)(5) define “pattern of activity” as “any combination of two or more separate instances of sexual abuse or exploitation of a minor by the defendant....” U.S.S.G. § 202.2(b)(6) (emphasis added). The district court based the enhancement on three instances of past conduct, but not on Melchor’s conduct with J.S. Specifically, the district court remarked, “the situation with the Oregon girl is not taken into account in the guideline range.” It then imposed a sentence ninety-eight months above the top of Mel-chor’s Guidelines range.
But Guideline § 2G2.2(b)(5) does cover Melchor’s conduct with J.S. Under § 2G2.2(b)(5), “[sjexual abuse or exploitation” can mean conduct described in 18 U.S.C. §§ 2422 (coercion and enticement) or 2423 (transportation of minors). U.S.S.G. § 2G2.2(b)(5). Melchor’s Face-book chats with J.S. revealed:
Mr. Melchor mailed J.S. a birthday card with $25.00, and also included a post-it note with his address written on it; sexual conversations, to include Mr. Mel-chor messaging [sic] her breasts, shaving her pubic hair, and making babies with her; Mr. Melchor’s acknowledgement of J.S.’s age; ... discussion about ... Mr. Melchor and J.S. meeting in person; and Mr. Melchor’s desire to be with J.S. and make babies.
According to Melchor’s plea agreement, the Government believed that his conduct with J.S. qualified as an offense under both §§ 2422 and 2423, though it agreed not to bring these charges in exchange for his plea. Thus, Melchor’s conduct with J.S. was one more additional instance of sexual abuse or exploitation of a minor under the pattern of activity enhancement.2 And by its terms, Guideline § 2G2.2(b)(5) imposes the large five-level increase for “any combination of two or more separate instances of sexual abuse or exploitation” of a minor. U.S.S.G. § 2G2.2(b)(5) (emphasis added).
*449In Aleo, the district court imposed a substantial upward variance after concluding that the Guidelines did not account for the seriousness of the defendant’s conduct. 681 F.3d at 300. There, the defendant pleaded guilty to multiple crimes related to possessing and transporting child pornography. Id. at 293. One of the crimes involved him recording his molestation of his five-year-old granddaughter. Id. at 294. At the sentencing, the district court said it “believed the guidelines could not possibly have envisioned a crime as horrendous as Aleo’s.” Id. Thus, the district court concluded, “ ‘there’s no way that the sentencing guidelines are adequate....’” Id. at 297. It went on to impose a sentence 427 months above the top of Aleo’s Guidelines range. Id.
But the Guidelines did cover Aleo’s crimes. Id. at 300 (Aleo’s Guidelines calculation “included several enhancements that specifically addressed the unique characteristics of his offense.”). Thus, we held that the district court imposed a substantively unreasonable sentence because its justification for the variance was based on factors already envisioned by the Guidelines. Id.
Like the district court in Aleo, here the district court imposed an upward variance, in part, because it believed that Melchor’s conduct with J.S. was not covered by the Guidelines. The Government says that the district court imposed an upward variance on Melchor because the pattern of activity enhancement did not fully represent the extent of Melchor’s pattern of sexual abuse of children, or because Melchor’s criminal history category substantially underrepresented the seriousness of his criminal history. But those were not the justifications offered by the district court. At the sentencing, the district court said the “the situation with the Oregon girl is not taken into account in the guideline range.” Thus, because Guideline § 2G2.2(b)(5) already accounted for Melchor’s conduct with J.S., the district court erred in concluding that the Guidelines did not cover that conduct. Consequently, Aleo governs the instant case, and the district court imposed the upward variance without compelling justification.
Further, Melchor’s conduct with J.S. is not “substantially in excess of’ the type of conduct ordinarily involved in cases like this. U.S. S.G. § 5K2.0(a)(3). Under § 5K2.0(a)(3), a district court may depart from the Guidelines, in an “exceptional case,” even though the conduct that “forms the basis for the departure is taken into consideration in determining the guidelines range.” Id. But, to justify such departure, the court must determine “that such circumstance is present ... to a degree substantially in excess of ... that which ordinarily is involved in that kind of offense.” Id. Here, the district court based the pattern of activity enhancement on three instances of past conduct, but not on Melchor’s conduct with J.S. Counting Melchor’s conduct with J.S. would result in only four instances of conduct under the § 2G2.2(b)(5) enhancement. Because § 2G2.2(b)(5) applies for “any combination of two or more separate instances” of conduct, the four instances do not make Mel-chor’s case so exceptional as to justify an upward departure. U.S.S.G. § 2G2.2(b)(5) (emphasis added).
At sentencing, the district court appropriately found that Melchor’s apparent lack of rehabilitation potential also warranted an upward variance. But the district court’s explanation did not say how much the variance resulted from Melchor’s conduct with J.S. — which had already been counted under § 2G2.2(b)(5) — and how much of the variance resulted from Mel-chor’s lack of rehabilitation potential. Thus, we remand to the district court to *450consider what sentence is appropriate without consideration of Melchor’s conduct with J.S.
III. CONCLUSION
For the reasons above, we VACATE Melchor’s sentence and REMAND for re-sentencing.
. The Government does not argue that Mel-chor’s conduct with J.S. falls outside of §§ 2422 or 2423.